题目描述
- 请实现一个函数用来匹配包括'.'和'*'的正则表达式
- 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）
- 在本题中，匹配是指字符串的所有字符匹配整个模式。
- 例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
题目解读
代码
#include<iostream>
using namespace std;
class Solution {
public:
bool matchCore(char* str, char* pattern, int s, int p){
// 此时 str 和 pattern 都已到末尾，相互匹配
if(str[s] == '\0' && pattern[p] == '\0'){
return true;
}
// 此时str没有到末尾，但是pattern到达末尾，则不匹配，返回false
if(str[s] != '\0' && pattern[p] == '\0'){
return false;
}
// -------------
// 在这里，可能有小伙伴要问了，为啥没有 str[s] == '\0' && pattern[p] != '\0') 这种情况呢?
// 其实这种情况是存在的，比如当 str 匹配结束，但是pattern没有结束,
// １、str="bbbba" pattern=".*a*a*" 当str到达末尾时，pattern后面的 a* 可以忽略，匹配正确
// 2、 str="bbbba" pattern=".*abb" 当str到达末尾时，pattern后面的 bb 不可以忽略，匹配不正确
// 无论是上面的哪种情况，pattern 都可以往后进行比较，如果是1则pattern可以走到'\0' 则成功匹配
// 如果是2，则pattern走不到 '\0'，则不能成功匹配
// --------------
// 当前元素匹配正确，递归进入下一个元素的比较
if(str[s] == pattern[p] || (str[s] != '\0' && pattern[p] == '.')){
return matchCore(str, pattern, s+1, p+1);
}
else{
// 3种情况
// 1、当前位置是 '*'
if(pattern[p] == '*'){
//这种情况下又分两种情况
// 1.1、比如 pattern为 ab*b*a 当前指针在第一个 '*' 那里，在这里要分三种情况
// 第一、向左走一步，考虑此*之前的元素可能出现多次
// 第二、向右走一步，认为*之前元素不再出现了，直接比较下一个元素，即认为第二个b*中的ｂ有可能出现一次或多次
// 第三、向右走两步，忽略第二个b*，即考虑第二个b*不出现情况
if(pattern[p+2] == '*'){
return matchCore(str, pattern, s, p-1) || matchCore(str, pattern, s, p+1) || matchCore(str, pattern, s, p+2) ;
}
// 1.2、比如 pattern为 ab*a 当前指针在 '*' 那里，在这里要分两种情况，向左走一步(认为此*之前一个元素出现多次)、
// 向右走一步(认为*之前元素不再出现了，直接比较下一个元素)
else{
return matchCore(str, pattern, s, p-1) || matchCore(str, pattern, s, p+1);
}
}
else{
// 2、当前位置不是 '*' 但后面是 '*' ; 首先当前位置不是*即证明当前位置和str中的相应元素不匹配，而当前元素下一位为*，
// 即证明当前位置可以出现0或多次，易知当前位置必须出现0次才有可能匹配成功过。因此当前位置和后面的*需要忽略，进入下一轮直接比较*之后的元素
if(pattern[p+1] == '*'){
return matchCore(str, pattern, s, p+2);
}
// 3、当前位置不是 '*' 且后面不是 '*'，可知匹配不成功
else{
return false;
}
}
}
}
bool match(char* str, char* pattern){
if(str == NULL || pattern == NULL){
return false;
}
return matchCore(str, pattern, 0, 0);
}
};
main(){
Solution ss;
char str[] = "bbbba";
char pattern[] = ".*a*a";
cout<<ss.match(str, pattern)<<endl;
}
总结展望
- 被这道题目折磨了两天，攻克之后，思维确实得到提升，有成就感
