leetcode日记（34）通配符匹配

这道题做了很久很久……一开始我想用的方法是使用双指针，分别指向两数组，然后依次按照题目中的规则遍历，做了很久发现时间超限了！这是我最后超时的代码！

class Solution {
public:bool isMatch(string s, string p) {for(int i=0;i<s.size();i++){cout<<s<<" "<<p<<endl;if(s[i]!=p[i]&&p[i]!='?'&&p[i]!='*') return 0;if(s[i]==p[i]||(p[i]=='?'&&i<s.size())){bool g=isMatch(s.substr(i+1,s.size()),p.substr(i+1,p.size()));return g;}else if(p[i]=='*'){while(p[i+1]=='*'){p.erase(p.begin()+i+1);}for(int j=0;j<=s.size()-i;j++){if(isMatch(s.substr(i+j,s.size()),p.substr(i+1,p.size()))==1) return 1;}}else return 0;}if(s==""&&p!=""){while(p[0]=='*') p.erase(p.begin());if(p=="") return 1;}if(s!=""&&p=="") return 0;if(s==""&&p=="") return 1;return 0;}
};

然后看了一眼解析…发现了很新奇很简单的思路！就是用bool数组记录前n个字符串是否匹配，然后使用动态规划依次填写bool数组。

期间遇到了一个小困难，就是*符号可以对应0个字母，可以每次判断正确都查看后一个字母是否为*，如果是则下一个也为正确

代码如下：

class Solution {
public:bool isMatch(string s, string p){int x=s.size(),y=p.size();bool b[x+1][y+1];for(int i=0;i<=x;i++)for(int j=0;j<=y;j++) b[i][j]=0;b[0][0]=1;int g=1;while(p[g-1]=='*'&&g<=y){b[0][g]=1;cout<<0<<" "<<g<<endl;g++;}for(int j=1;j<=y;j++){for(int i=1;i<=x;i++){if(b[i-1][j-1]!=0){if(s[i-1]==p[j-1]||p[j-1]=='?'){b[i][j]=1;int u=j+1;while(p[u-1]=='*'&&u<=y){b[i][u]=1;u++;}}else if(p[j-1]=='*'){for(int o=i;o<=x;o++){b[o][j]=1;int u=j+1;while(p[u-1]=='*'&&u<=y){b[i][u]=1;u++;}}}}}}cout<<x<<" "<<y;return b[x][y];}
};