这题一年前就做过,当时刚开始刷leetcode,提交了几十次过不去,就放那没管了。今天剑指offer又遇到这题,终于做出来了,用的dp。
class Solution {
public:
bool isMatch(string s, string p) {
int s_len=s.size(),p_len=p.size();
vector<vector<bool>> dp(s_len+,vector<bool>(p_len+,false));
//dp[i][j]表示s[0,i-1]和p[0,j-1]能否匹配
dp[][]=true;//空串匹配空串
for(int i=;i<=p_len;++i){
dp[][i]=i> and p[i-]=='*' and dp[][i-];
}
for(int i=;i<=s_len;++i){
for(int j=;j<=p_len;++j){
if(p[j-]=='*'){
if(p[j-]!='.'){//数字+'*'
dp[i][j]=dp[i][j-] or (s[i-]==p[j-] and (dp[i-][j-] or dp[i-][j-]));
}
else{//'.'+'*'
for(int k=i;k>= ;--k){
if(dp[k][j-]){
dp[i][j]=true;
break;
}
}
}
}
else if(p[j-]=='.'){
dp[i][j]=dp[i-][j-];
}
else{//数字
dp[i][j]=p[j-]==s[i-] and dp[i-][j-];
}
}
}
return dp.back().back();
}
};