44. 通配符匹配

44. 通配符匹配

字符串dp

类似的还有经典的72. 编辑距离
本题是10. 正则表达式匹配的稍简单版本

dp[i][j]表示以前i-1个s和前j-1个p是否匹配

class Solution {
public:
    bool isMatch(string s, string p) {
        int n=s.size(),m=p.size();
        bool dp[n+1][m+1];
        memset(dp,0,sizeof dp);
        dp[0][0]=true;
        
        for(int j=1;j<=m;j++){
            if(p[j-1]=='*')
                dp[0][j]=dp[0][j-1];
        }
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s[i-1]==p[j-1] || p[j-1]=='?')
                    dp[i][j]=dp[i-1][j-1];
                else if(p[j-1]=='*'){
                    // 直接废弃掉*，意思是*选0次
                    dp[i][j]|=dp[i][j-1];
                    // 用上*，意思是*肯定能和和s[i-1]匹配
                    dp[i][j]|=dp[i-1][j];
                }
            }
        }
        return dp[n][m];
    }
};