10. 正则表达式匹配
难度困难2981
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
代码语言：javascript复制输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。示例 2:
代码语言：javascript复制输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3：
代码语言：javascript复制输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。提示：
1 <= s.length <= 201 <= p.length <= 30s只包含从a-z的小写字母。p只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
bool isMatchEmpty(string s, string p) {
if(p.empty()&&s.empty())return true;
if(p.back()!='*')return false;
if(p.size()>=2&&p.back()=='*'){
return isMatchEmpty(s,p.substr(0,p.size()-2));
}
return false;
}
bool isMatch(string s, string p) {
if(p.empty()&&s.empty())return true;
if(p.empty()&&!s.empty())return false;
//s='' p="a*" ".*"或者其他不符合情况
if(s.empty()){
return isMatchEmpty(s,p);
}
int psize=p.size()-1;
int ssize=s.size()-1;
//s="x" p="." ||p="x"
//s.back()这个开始错了
//if(p.back()!='*'&&(p.back()==s.back() ||s.back()=='.')){
if(p.back()!='*'&&(p.back()==s.back() ||p.back()=='.')){
return isMatch(s.substr(0,ssize),p.substr(0,psize));
}
bool ret=false;
if(ret==false&&p.back()=='*'&&p.size()>=2){
//a=abcxx p=abcx* ||abc.*
//结尾是*或者结尾相同
if(p[psize-1]==s[ssize]||p[psize-1]=='.')
//这个地方又抄错了
//return isMatch(s.substr(0,ssize),p);
{
ret= isMatch(s.substr(0,ssize),p);
//cout<<s.substr(0,ssize)<<ssize<<ret<<endl;
}
//ret=false && 这个地方丢了一个=
if(ret==false && ( p[psize-1]==s[ssize] || p[psize-1]=='.' )){
ret=isMatch(s,p.substr(0,psize-1));
cout<<p.substr(0,psize-1)<<psize<<ret<<endl;
}
}
if(false==ret&&p.back()=='*'&&p.size()>=3&&s.size()>=1){
//s = "abcx" p ="abcxz*" p = "abc.z*"
if (p[psize - 1] != s[ssize] && (p[psize - 2] == s[ssize] || p[psize - 2] == '.' )) {
ret = isMatch(s.substr(0, ssize ), p.substr(0,psize-2));
}
//s = "abcx" p ="abcxz*" p = "abc.z*"
if (ret ==false && p[psize - 1] != s[ssize]) {
ret = isMatch(s, p.substr(0, psize - 1));
}
}
return ret;
}
