题解 | #通配符匹配#
通配符匹配
http://www.nowcoder.com/practice/e96f1a44d4e44d9ab6289ee080099322
题意：
方法：
动态规划
思路：dp[i][j]表示字符串s的前i个字符与字符串p的前j个字符是否匹配。
状态转移方程：
1.当s[i-1]==p[j-1] || p[j-1]=='?'时，则匹配；
2.当p[j-1]=='*'时，则匹配空或单个字符；
3.否则，匹配失败。
class Solution {
public:
bool isMatch(const char *s, const char *p) {
int n1=strlen(s),n2=strlen(p);
int dp[1005][1005]={0};//dp[i][j]表示字符串s的前i个字符与字符串p的前j个字符是否匹配
dp[0][0]=1;//初始化
for(int i=1;i<=n2;i++){
dp[0][i]=dp[0][i-1]&&(p[i-1]=='*');
}
for(int i=1;i<=n1;i++){//二重循环
for(int j=1;j<=n2;j++){
if(s[i-1]==p[j-1]||p[j-1]=='?'){//当s[i-1]==p[j-1]||p[j-1]=='?'时，则匹配
dp[i][j]=dp[i-1][j-1];
}else if(p[j-1]=='*'){//当p[j-1]=='*'时，则匹配空或至少一个字符
dp[i][j]=dp[i][j-1]||dp[i-1][j];
}else{//否则，匹配失败
dp[i][j]=0;
}
}
}
return dp[n1][n2]==1?true:false;
}
};
时间复杂度：%2C%E4%BA%8C%E9%87%8D%E5%BE%AA%E7%8E%AF%E9%81%8D%E5%8E%86%E3%80%82)
空间复杂度：%2C%E5%AD%98%E5%82%A8%E4%BA%8C%E7%BB%B4dp%E6%95%B0%E7%BB%84%E3%80%82)
查看14道真题和解析
