算法1

$O(n*m)$

dp[i][j] 表示s以i结尾, p以j结尾是否匹配.

C++ 代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size();
        int m = p.size();
        vector<vector<bool>> dp(n + 1, vector<bool> (m + 1, false));
        dp[0][0] = true;
        // 是否能变成空串
        for (int j = 1; j <= m; ++j) {
            if (p[j - 1] == '*' && dp[0][j - 2]) {
                dp[0][j] = true;
            } 
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                    if (j >= 2) {
                        dp[i][j] = dp[i][j] | dp[i][j - 2];
                    }
                    // if (j >= 2) {
                    //     dp[i][j] = dp[i][j] | dp[i][j - 2];
                    // }
                    // for (int k = 1; i - k >= 0 && (s[i - k] == p[j - 2] || p[j - 2] == '.'); ++k) {
                    //     dp[i][j] = dp[i][j] | dp[i - k][j - 2];
                    // }
                }
            }
        }
        return dp[n][m];
    }
};