dp

g(i, j)表示f(0, j) | f(1, j)…f(i, j)

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

滚动数组优化

class Solution {
public:
    bool isMatch(string s, string p) {
        const int n = s.size();
        const int m = p.size();
        vector<vector<bool> > f(n + 1, vector<bool>(m + 1));
        vector<bool> g(m + 1);
        f[0][0] = g[0] = true;
        for(int j = 1; j <= m && p[j - 1] == '*'; j++) f[0][j] = g[j] = true;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(s[i - 1] == p[j - 1] || p[j - 1] == '?'){
                    f[i][j] = f[i][j] | f[i - 1][j - 1];
                }
                else if(p[j - 1] == '*'){
                    f[i][j] = f[i][j] | g[j - 1];
                }
                g[j] = g[j] | f[i][j];
            }
        }
        return f[n][m];
    }
};