10. Regular Expression Matching

O(mn) time O(m+n) space
只有p[n - 1]为*那种情况才有可能需要向两个方向递归（其他单向递归的时间复杂度不会超过这个），一个方向m层，另外一个方向n层，对于每一层都有可能向另外一个方向递归，所以时间复杂度是O(mn)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        f = [[False] * (n + 1) for i in range(m + 1)]
        f[0][0] = True
        for i in range(1, n + 1):
            f[0][i] = (p[i - 1] == '*') and f[0][i - 2]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    f[i][j] = f[i][j - 2] or (f[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.'))
                else:
                    f[i][j] = f[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')
        return f[m][n]

class Solution {
public:
    bool isMatch(string s, string p) {
        return isMatch(s, s.length(), p, p.length()); // 从后往前分析
    }

    bool isMatch(const string &s, int m, const string &p, int n) {
        if (m == 0 && n == 0) return true; // 两个空串肯定匹配
        if (m != 0 && n == 0) return false; // 如果s不空p空肯定不匹配
        if (m == 0 && n != 0) return p[n - 1] == '*' && isMatch(s, m, p, n - 2); // 如果s空p不空，则只有可能p是类似a*a*a*这样的
        if (p[n - 1] == '*') return (s[m - 1] == p[n - 2] || p[n - 2] == '.') && isMatch(s, m - 1, p, n) || isMatch(s, m, p, n - 2); // 如果p以*结尾，则(1)要不s[m - 1]跟p[n - 2]匹配（包括p[n - 2]是.的情况）并且s[0:m-1)和p[0:n)匹配（这里之所以是p[0:n)不是p[0:n-2)是因为s[0:m-1)未必能跟p[0:n-2)匹配但是有可能跟p[0:n)匹配，比如s是xxxzz，p是xxxz*，xxx跟xxxz不匹配但是xxxz*可以跟xxxz匹配，所以这里要用整个p去尝试匹配s[0:m-1)）(2)要不s[0:m)跟p[0:n - 2)匹配
        return (s[m - 1] == p[n - 1] || p[n - 1] == '.') && isMatch(s, m - 1, p, n - 1); // 如果p不以*结尾，则s[m - 1]跟p[n - 1]匹配（或者p[n - 1]为.）并且s[0:m-1)跟p[0:n-1)匹配
    }
};

dp O(mn) time O(mn) space
这道题中”a*”的意思是若干个a

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1));
        f[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            f[0][j] = (p[j - 1] == '*') && f[0][j - 2];
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i][j - 2] || f[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.');
                } else {
                    f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }
        return f[m][n];
    }
};

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length(), m = p.length();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
        dp[0][0] = true; // 两个空串肯定匹配
        for (int j = 1; j <= m; ++j) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2]; // 前一个字符p[j - 2]相当于循环节，所以要继承前前个结果，即循环节之前的匹配结果
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1]; // 如果字符相同或者正则字符是.直接继承之前两个串的匹配结果
                } else if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.')); // 因为p[j - 2]是循环节，所以要检查前前个结果dp[i][j - 2]，即循环节之前的匹配结果；另外，如果之前的字符串s[0:i-2]已经和p[0:j-1]匹配，即dp[i - 1][j]为true，那么就要看当前字符是否和正则字符（循环节p[j-2]）匹配；这里一定要考虑清楚逻辑！！用OR是对的，ifelse可能出问题
                }
            }
        }
        return dp[n][m];
    }
};