10. Regular Expression Matching

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> memo(m + 1, vector<bool>(n + 1, false));
        memo[0][0] = true;
        for (int j = 1; j <= n; j++)
            memo[0][j] = p[j - 1] == '*' && ((j > 1 && memo[0][j - 2]) || j == 1);

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] != '*')
                    memo[i][j] = memo[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]);
                else {
                    memo[i][j] = (j >= 2 && memo[i][j - 2]) || memo[i][j - 1] || (j >= 2 && memo[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
            //f[i][j] = f[i][j - 2] || (s[i - 1] == p[j - 2] || '.' == p[j - 2]) && f[i - 1][j];
            //some overlapping cases here I can't figure it out
                }
            }

         for (int i = 0; i <= m; i++) {cout<<endl;
            for (int j = 0; j <= n; j++) cout<<memo[i][j];}


        return memo[m][n];
    }
};