1
class Solution {
2
 public:
3
  bool match(int i, int j, string &a, string &b, vector<vector<int>> &dp) {
4
    if (i < 0 && j < 0) return true;
5
    if (i >= 0 && j < 0) return false;
6
    if (i < 0 && j >= 0) {
7
      for (; j > -1; j--)
8
        if (b[j] != '*') return false;
9
      return true;
10
    }
11
    if (dp[i][j] != -1) return dp[i][j];
12
    if (a[i] == b[j] || b[j] == '?') return dp[i][j] = match(i - 1, j - 1, a, b, dp);
13
    if (b[j] == '*') return dp[i][j] = (match(i - 1, j, a, b, dp) | match(i, j - 1, a, b, dp));
14
    return false;
15
  }
16
  bool isMatch(string s, string p) {
17
    int n = s.size(), m = p.size();
18
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
19
    return match(n - 1, m - 1, s, p, dp);
20
  }
21
};