Untitled
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...