LC

题目

思路

一道字符串DP题，优化思路类似于完全背包。

图1
图2

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        vector<vector<bool>> dp = vector(n + 1, vector<bool>(m + 1));
        s = ' ' + s, p = ' ' + p;
        dp[0][0] = true;

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

    }
};