44. Wildcard Matching

backtracking best case O(m+n) time O(1) space
worst case O(mn)

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        int i = 0, j = 0, ist = -1, jst = -1;
        while (i < m) {
            if (j < n && (s[i] == p[j] || p[j] == '?')) {
                ++i;
                ++j;
            } else if (j < n && (p[j] == '*')) { // 保存*匹配到的i和j
                ist = i;
                jst = j++;
            } else if (ist >= 0) { // 如果之前匹配过*
                i = ++ist; // 这里重置到ist的下一个是因为*有可能匹配多个字符，方便重置i
                j = jst + 1; // backtracking假设*可以cover之前的ist那个字符，继续尝试匹配之后的字符
            } else return false;
        }
        while (j < n && p[j] == '*') { // 只有p后边全是*才说明完全匹配上了
            ++j;
        }
        return j == n;
    }
};

dp O(mn) time O(mn) space

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for i in range(1, n + 1):
            f[0][i] = p[i - 1] == '*' and f[0][i - 1]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    f[i][j] = f[i][j - 1] or f[i - 1][j]
                else:
                    f[i][j] = f[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '?')
        return f[m][n]

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length(), m = p.length();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        f[0][0] = true; // 两个空串肯定匹配
        for (int j = 1; j <= m; ++j) {
            f[0][j] = f[0][j - 1] && (p[j - 1] == '*'); // *可以匹配任意多个字符，所以直接继承前一个的结果
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i][j - 1] || f[i - 1][j]; // s[i - 1]不去跟*匹配，看s[0:i-1]和p[0:j-2]是否匹配；s[i - 1]去跟*匹配，看s[0:i-2]和p[0:j-1]是否匹配
                } else {
                    f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?'); // 两字符相同（或通配符是?）直接查看之前的匹配结果
                }
            }
        }
        return f[n][m];
    }
};

recursive

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        cache.resize(m + 1, vector<int>(n + 1, -1));
        return f(m, n, s, p);
    }

    bool f(int i, int j, const string &s, const string &p) {//cout<<i<<" "<<j<<endl;
        if (i == 0 && j == 0) return true;
        if (i > 0 && j < 1) return false;
        if (cache[i][j] != -1) return cache[i][j];
        if (i == 0) return cache[i][j] = p[j - 1] == '*' && f(i, j - 1, s, p);
        if (p[j - 1] == '*') return cache[i][j] = f(i, j - 1, s, p) || f(i - 1, j, s, p);
        return cache[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && f(i - 1, j - 1, s, p);
    }

    vector<vector<int>> cache;
};