10. 正则表达式匹配

10. 正则表达式匹配

字符串dp

类似的还有经典的72. 编辑距离
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=2;j<=m;j++){
            if(p[j-1]=='*')
                dp[0][j]=dp[0][j-2];
        }
        
        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]=='*'){
                    if(j>=2){
                        // 直接废弃掉c*，意思是c选0次
                        dp[i][j]|=dp[i][j-2];
                        // 用上c，意思是和s[i-1]匹配的话，
                        // 如果s[0~i-2]和p[0~i-1]匹配成功，那么这次也成功
                        if(s[i-1]==p[j-2] || p[j-2]=='.')
                            dp[i][j]|=dp[i-1][j];
                    }
                }
            }
        }
        return dp[n][m];
    }
};