题目
我的思路
我的解决思路是深搜递归，可是需要注意时间复杂度，不同的深搜3^n与2^n的复杂度差别还是蛮大的。
下面结合官方题解，阐述一下两种思路：
思路一：深搜递归
时间复杂度是2^n，空间复杂度是n（可能同时存在n次递归调用层）。
class Solution { public: bool isMatch(string s, string p) { if(p.empty()) return s.empty(); if(p[1] == '*'){ return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.')) && isMatch(s.substr(1), p); } else{ return !s.empty() && (s[0] == p[0] || p[0] == '.') && (isMatch(s.substr(1), p.substr(1))); } } }; 作者：jarvis1890 链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/zheng-ze-biao-da-shi-pi-pei-di-gui-qiu-jie-by-jarv/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
思路二：动态规划（神！）
class Solution { public boolean isMatch(String A, String B) { int n = A.length(); int m = B.length(); boolean[][] f = new boolean[n + 1][m + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { //分成空正则和非空正则两种 if (j == 0) { f[i][j] = i == 0; } else { //非空正则分为两种情况 * 和 非* if (B.charAt(j - 1) != '*') { if (i > 0 && (A.charAt(i - 1) == B.charAt(j - 1) || B.charAt(j - 1) == '.')) { f[i][j] = f[i - 1][j - 1]; } } else { //碰到 * 了，分为看和不看两种情况 //不看 if (j >= 2) { f[i][j] |= f[i][j - 2]; } //看 if (i >= 1 && j >= 2 && (A.charAt(i - 1) == B.charAt(j - 2) || B.charAt(j - 2) == '.')) { f[i][j] |= f[i - 1][j]; } } } } } return f[n][m]; } } 作者：jerry_nju 链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/zhu-xing-xiang-xi-jiang-jie-you-qian-ru-shen-by-je/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
时间复杂度是m*n,空间复杂度也是m*n
我的实现
class Solution { public: //动态规划：f[i][j]表示主串的前i+1（0~i）个字符能否由模式串的前j+1（0~j）个字符匹配 /* 模式串p[j]是'*',那么f[i][j]=f[i][j-2]||f[i][j-1]||(s[i]==s[i-1]&&(f[i-1][j-1]||f[i-1][j]))||(p[j-1]=='.'&&(f[i-1][j-1]||f[i-1][j])) 模式串p[j]是'.',那么f[i][j]=f[i-1][j-1]; 模式串p[j]是others,那么f[i][j]=f[i-1][j-1]&&s[i]==p[j] */ bool isMatch(string s, string p) { //给模式字符串去重 //bool[][] f = new bool[][](s.size()+1,p.size()+1); bool f[s.size()+1][p.size()+1]; f[0][0]=true; //return f[0][0]; for(int j = 1;j<=p.size();j++){ if(j==1)f[0][j]=false; else if(j>=2){ if(p[j-1]=='*'){ f[0][j] = f[0][j-2]||f[0][j-1]; //cout<<f[0][j]<<" j:"<<j<<endl; }else{ f[0][j] = false; } } } for(int i = 1;i<=s.size();i++){ f[i][0]=false; } for(int i = 1;i<=s.size(); i++){ for(int j = 1; j<=p.size();j++){ //cout<<"check???"<<endl; if(p[j-1]=='*'){ if(i==1)f[i][j]=f[i][j-2]||f[i][j-1]||(p[j-2]=='.'&&(f[i-1][j-1]||f[i-1][j]));else f[i][j]=f[i][j-2]||f[i][j-1]||(s[i-2]==s[i-1]&&s[i-1]==p[j-2]&&(f[i-1][j-1]||f[i-1][j]))||(p[j-2]=='.'&&(f[i-1][j-1]||f[i-1][j])); }else if(p[j-1]=='.'){ f[i][j]=f[i-1][j-1]; }else { f[i][j] = f[i-1][j-1]&&s[i-1]==p[j-1]; } } } //cout<<f[0][0]<<f[0][1]<<f[0][2]<<" "<<f[1][0]<<f[1][1]<<f[1][2]<<" "<<f[2][0]<<f[2][1]<<f[2][2]<<endl; int a = s.size(); int b = p.size(); return f[a][b]; } }; /* 我的做法通过了部分测试用例，但是时间复杂度太高了，遇到仅最后一个字符不能匹配，而的字符前面存在多种匹配方式的用例，会发生超时。 比如："aaaaaaaaaab" "a*a*a*a*a*a*a*a*a*a*c" 经过改进（在深搜递归出口处增加一点判断），深搜的复杂度从3^n降到了2^n通过了所有用例。 深搜 每次读取两个字符，如果被读取的第二个字符不是*那么回退一个字符。 6种情况：第一个字符是否是. ,第二个字符是否是* ，第一个字符是否与待匹配字符相同。 否否否，返回false； 否否是，continue； `否是否，continue； `否是是，深搜continue/深搜指针再回退一个字符continue； 是否，continue； 是否，不存在（continue）； `是是，深搜指针再回退一个字符，并把‘.’改成待匹配字符，continue class Solution { public: bool search(string &s,string &p,int s_it,int p_it){ if(s.size()==s_it ){ if(p_it==p.size())return true; } if(p.size()==p_it)return false; cout<<"s:"<<s[s_it]<<" p:"<<p[p_it]<<endl; if(p.size()-1>p_it){//如果存在两个未匹配的模式字符 if(p[p_it+1]=='*'){//如果第二个字符是* if(p[p_it]=='.'){//是是 if(search(s,p,s_it+1,p_it+2)==true)return true; if(search(s,p,s_it+1,p_it)==true)return true; if(search(s,p,s_it,p_it+2)==true)return true; }else{ if(p[p_it] == s[s_it]){//否是是 if(search(s,p,s_it+1,p_it+2)==true)return true; if(search(s,p,s_it+1,p_it)==true)return true; if(search(s,p,s_it,p_it+2)==true)return true; }else{//否是否 return search(s,p,s_it,p_it+2); } } } } {//如果只有一个未匹配的模式字符 or 如果第二个字符不是* if(p[p_it]!='.'){ if(p[p_it]!=s[s_it]) //否否否 return false; else//否否是 return search(s,p,s_it+1,p_it+1); }else{//是否 return search(s,p,s_it+1,p_it+1); } } } bool isMatch(string s, string p) { //给模式字符串去重 for(int i = 0;i<s.size();i++){ } return search(s,p,0,0); } }; 下面这个深搜不会发生超时 class Solution { public: bool search(string &s,string &p,int s_it,int p_it){ if(s.size()==s_it ){ if(p_it==p.size())return true; if((p.size()-p_it)%2!=0){ return false; }else{ int k; for(k=p_it+1;k<p.size();k+=2){ if(p[k]!='*')return false; } return true; } } if(p.size()==p_it)return false; //cout<<"s:"<<s[s_it]<<" p:"<<p[p_it]<<endl; if(p.size()-1>p_it){//如果存在两个未匹配的模式字符 if(p[p_it+1]=='*'){//如果第二个字符是* if(p[p_it]=='.'){//是是 //if(search(s,p,s_it+1,p_it+2)==true)return true; if(search(s,p,s_it+1,p_it)==true)return true; if(search(s,p,s_it,p_it+2)==true)return true; }else{ if(p[p_it] == s[s_it]){//否是是 //if(search(s,p,s_it+1,p_it+2)==true)return true; if(search(s,p,s_it+1,p_it)==true)return true; if(search(s,p,s_it,p_it+2)==true)return true; }else{//否是否 return search(s,p,s_it,p_it+2); } } } } {//如果只有一个未匹配的模式字符 or 如果第二个字符不是* if(p[p_it]!='.'){ if(p[p_it]!=s[s_it]) //否否否 return false; else//否否是 return search(s,p,s_it+1,p_it+1); }else{//是否 return search(s,p,s_it+1,p_it+1); } } } bool isMatch(string s, string p) { //给模式字符串去重 return search(s,p,0,0); } }; */
拓展学习
加快速度，刻意练习速度！一定要在上午12点之前弄完每日一题