for John B

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];
    }
};