DP

$ 时间复杂度O(NM)，空间复杂度O(NM)$

参考文献

lc究极班

AC代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        vector<vector<bool>> f (n + 1, vector<bool> (m + 1, false));
        s  = ' ' + s; p = ' ' + p;
        f[0][0] = true;//两个字符串都空，匹配
        //s从0枚举是因为*可以代表0个字符
        for (int i = 0 ; i <= n ; i ++){
            for (int j = 1 ; j <= m ; j ++){
                if (i && p[j] != '*'){
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?');
                } else if (p[j] == '*'){
                    f[i][j] = f[i][j - 1] || i && f[i - 1][j];
                }
            }
        }
        return f[n][m];

    }
};