算法1

完全背包优化 + 闫氏dp分析

时间复杂度 O（m * n）

参考文献

C++ 代码

class Solution {
public:
    string bs, bp;
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;
        bs = s, bp = p;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1, false));
        f[0][0] = true;
        for(int i = 1; i <= m; ++ i) 
            if(bp[i] == '*')
                f[0][i] = f[0][i - 2];
        if(n && m) f[1][1] = match(1, 1);
        for(int i = 1; i <= n; ++ i)
            for(int j = 2; j <= m; ++ j)
               if(bp[j] != '*') f[i][j] = f[i - 1][j - 1] && match(i, j);
               else f[i][j] = f[i][j - 2] || (f[i - 1][j] && match(i, j - 1));
        return f[n][m];
    }

    bool match(int i, int j)
    {
        return bs[i] == bp[j] || bp[j] == '.';
    }
};