问题抽象

问模式串p是否能匹配字符串s。模式串中’.’匹配任意单个字符，’*’表示前一个字符可以有0或多个

算法：DP

这道题只问能不能匹配，容易想到用DP来做，且状态也好定义：f[i][j]表示s[1~i]能否匹配p[1~j]，平凡的转移也比较好想：f[i-1][j-1]转移到f[i][j], 只需s[i]==p[j] || p[j] == '.'

这道题的难点在于非平凡的状态转移，因为p中可能有’*’

关键在于分出两种选择：要么舍弃’*’和前一个字符，要么利用他们，这两种选择对应两种转移情况：

f[i][j]可能由f[i][j-2]转移过来（舍弃'*'和前一个字符） 比如s=aba, p=abac*由s=aba, p=aba转移过来

或者

f[i][j]可能由f[i-1][j]转移过来（利用'*'增加前一个字符）, 比如s=aaaaa, p=a*由s=aaaa和p=a*转移过来

注意，f[0][j]是有意义的，即p可以去匹配空字符串s(s = ‘’, p = ‘c*’)

时间复杂度

$O(NM)$

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> f(m+1, vector<bool>(n+1));

        s = " " + s;
        p = " " + p;
        f[0][0] = true;
        for(int i = 0; i <= m; i ++){
            for(int j = 1; j <= n; j ++){
                if(i > 0 && (s[i] == p[j] || p[j]=='.')){ // 直接匹配
                    f[i][j] = f[i][j] | f[i-1][j-1];
                }
                if(p[j] == '*'){
                    if(j >= 2){ // 丢弃'*'及前面一个字符
                        f[i][j] = f[i][j] | f[i][j-2];
                    }
                    if(i > 0 && (s[i]==p[j-1] || p[j-1] == '.')){ // 利用'*'及前面一个字符
                        f[i][j] = f[i][j] | f[i-1][j];
                    }
                }
            }
        }
        return f[m][n];
    }
};