# for John B

unknown
c_cpp
2 years ago
1.6 kB
4
Indexable
Never
```class Solution {
public:
bool isMatch(string s, string p) {
dp = vector<vector<int>>(s.size() + 1, vector<int>(p.size() + 1, -1));
for (int i = 1; i < s.size() + 1; i++) dp[i][0] = 0;
dp[0][0] = 1;
for (int i = 1; i < p.size() + 1; i++) {
dp[0][i] = 0;
if (p[i-1] == '*') // * means match zero or more, here we simulate matching zero.
dp[0][i] = dp[0][i-2];
}
return solve(s.size(), p.size(), s, p);
}
// dp is a 2d array that will store computed states to avoid re-computation
// values: 0 => false, 1 => true, -1 => not processed yet.
vector<vector<int>> dp;
int solve(int i, int j, string &s, string  &p) {
if (dp[i][j] != -1) return dp[i][j];
dp[i][j] = 0;
// if they single match, check previous sub-string recursively.
if (s[i-1] == p[j-1] || p[j-1] == '.') {
dp[i][j] = solve(i - 1, j - 1, s, p);
}
// solve for *
if (p[j-1] == '*') {
// zero value match: skip it. e.g. s = ...a , p = ...b* (it best to skip b* here)
int zero = solve(i, j - 2, s, p);
dp[i][j] = zero;
// if they don't match (e.g. the above comment example), you can return
if (!(p[j - 2] == s[i-1] || p[j - 2] == '.')) {
return dp[i][j];
}
// at this point, they do match (e.g. s = ...a, p = ...a*). So, check previous sub-strings recursively.
if (solve(i-1, j-2, s, p) || solve(i-1, j, s, p))
dp[i][j] = 1;
}
return dp[i][j];
}
};```