Untitled

 avatar
unknown
c_cpp
2 years ago
765 B
5
Indexable
class Solution {
public:
    string s, p;
    int n, m;
    int memo[2002][2002];

    bool dp(int i, int j) {
        if (j == m){
            if (i == n) return true;
            else return false;
        }

        int &ans = memo[i][j];
        if (ans != -1) return ans;

        if (i < n && (s[i] == p[j] || p[j] == '?')) {
            ans = dp(i + 1, j + 1);
        } else if (p[j] == '*') {
            ans = dp(i, j+1) || (i < n && dp(i+1, j));
        } else {
            ans = false;
        }
        return ans;
    }

    bool isMatch(string S, string P) {
        s = S;
        p = P;
        n = s.length();
        m = p.length();

        memset(memo, -1, sizeof(memo));

        return dp(0, 0);
    }
};
Editor is loading...