Leetcode 44. 通配符匹配（DAY 317）---- 后端面试题

• • 原题题目
  • 代码实现（首刷自解）

class Solution {
 public:
  bool Judge(vector>& dp, const string& s, const string& p, int spos, int ppos) {
    if (p[ppos - 1] == '*') return ppos == 1 || dp[spos][ppos - 1] || spos && (dp[spos - 1][ppos] || dp[spos - 1][ppos - 1]);
    if (!spos) return false;

    return dp[spos - 1][ppos - 1] && (s[spos - 1] == p[ppos - 1] || p[ppos - 1] == '?'); 
  }

  bool isMatch(string s, string p) {
    vector> dp(s.size() + 1, vector(p.size() + 1, false));

    int ssize = s.size(), psize = p.size();
    dp[0][0] = true;

    for (int i = 0; i <= ssize; ++i) {
      for (int j = 1; j <= psize; ++j) {
        if (Judge(dp, s, p, i, j)) {
          dp[i][j] = true;
        }
      }
    }
    return dp[ssize][psize];
  }
};