这题一年前就做过, 当时刚开始刷 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+1,vector<bool>(p_len+1,false));
- //dp[i][j] 表示 s[0,i-1] 和 p[0,j-1] 能否匹配
- dp[0][0]=true;// 空串匹配空串
- for(int i=1;i<=p_len;++i){
- dp[0][i]=i>1 and p[i-1]=='*' and dp[0][i-2];
- }
- for(int i=1;i<=s_len;++i){
- for(int j=1;j<=p_len;++j){
- if(p[j-1]=='*'){
- if(p[j-2]!='.'){// 数字 +'*'
- dp[i][j]=dp[i][j-2] or (s[i-1]==p[j-2] and (dp[i-1][j-2] or dp[i-1][j-1]));
- }
- else{//'.'+'*'
- for(int k=i;k>= 0;--k){
- if(dp[k][j-2]){
- dp[i][j]=true;
- break;
- }
- }
- }
- }
- else if(p[j-1]=='.'){
- dp[i][j]=dp[i-1][j-1];
- }
- else{// 数字
- dp[i][j]=p[j-1]==s[i-1] and dp[i-1][j-1];
- }
- }
- }
- return dp.back().back();
- }
- };
来源: http://www.bubuko.com/infodetail-3415602.html