题目描述
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
题目链接： https://leetcode-cn.com/problems/regular-expression-matching/
思路
使用递归来做。使用两个指针 sPos 和 pPos 分别表示 s 和 p 的当前进行匹配位置，sPos 和 pPos 均初始化为 0。
如果 p[pPos] == '.'，因为 '.' 能匹配任意单个字符，所以将 sPos+1、pPos+1 匹配下一个字符即可。
如果模式串 p 当前字符的下一个字符也就是 p[pPos+1]=='*'，那么：
- 如果 s[sPos] 和 p[pPos] 可以匹配：
- 可以将 sPos 保持不动，将 pPos 后移两个位置，例如 s="aa", p="a*aa"；
- 也可以将 sPos 后移一个位置，而 pPos 保持不动，例如 s="aaaaa", p="a*"；
- 否则：
- 将 sPos 保持不动，将 pPos 后移两个位置，例如 s="aab", p="b*aab"；
在写代码的时候，要根据模式串 p 当前字符的下一个字符也就是 p[pPos+1] 是否为 '*' 分两种情况讨论，具体如下：
class Solution {
public:
bool isMatch(string s, string p) {
int sPos = 0, pPos = 0;
return match(s, p, sPos, pPos);
}
bool match(string& s, string& p, int sPos, int pPos){
int lens = s.length(), lenp = p.length();
if(sPos>=lens && pPos>=lenp) return true;
if(sPos>lens || pPos>=lenp) return false; // 注意这个条件
if(pPos+1<lenp && p[pPos+1]=='*'){
if(sPos==lens || s[sPos]==p[pPos] || p[pPos]=='.'){
return match(s, p, sPos, pPos+2) || // 不匹配直接跳过
match(s, p, sPos+1, pPos); // 匹配一个或多个字符
}else return match(s, p, sPos, pPos+2);
} else {
if(sPos==lens) return false;
if(s[sPos]==p[pPos] || p[pPos]=='.') return match(s, p, sPos+1, pPos+1);
else return false;
}
}
};
需要注意的是返回的条件是 sPos>lens || pPos>=lenp，而不是 sPos>=lens || pPos>=lenp，因为可能会出现 s="a"，p="ab*" 的情况。还有一点要注意的是 match 函数的前两个字符串参数要使用引用，不然会超时。
用指针写代码会更简洁：
class Solution {
public:
bool isMatch(string s, string p) {
int sPos = 0, pPos = 0;
return match(s.data(), p.data());
}
bool match(char* s, char* p){
if(!*s && !*p) return true;
if(*s && !*p) return false;
if(*(p+1)=='*'){
if(*s == *p || (*p == '.' && *s != ' ')) return match(s, p + 2) || match(s + 1, p);
else return match(s, p + 2);
}else{
if(*s==*p || (*p=='.' && *s!=' ')) return match(s+1, p+1);
else return false;
}
}
};
参考
1、https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-whyatlc-2/
2、https://leetcode-cn.com/problems/regular-expression-matching/solution/cjian-ji-dai-ma-ti-jie-ming-tian-xie-by-orangeman/