题解 | #通配符匹配#

动规
设dp[i][j]表示s[:i]和p[:j]匹配，状态转移方程：
（1）p[j] == '', dp[i][j] = dp[i - 1][j] || dp[i - 1][j - 1] || dp[i][j - 1]; //匹配n次或1次或0次
（2）p[j] == '?' || s[i] == p[j]:
dp[i][j] = dp[i - 1][j - 1];
边界：
p的前缀为‘’的时候，dp[0][i]=true！
时间复杂度：
空间复杂度：

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if(s == NULL && p == NULL) return true;
        if(s == NULL || p == NULL) return false;
        int m = strlen(s), n = strlen(p);
        bool dp[m + 1][n + 1];
        memset(dp, false, sizeof(dp));
        dp[0][0] = true;
        for(int i = 1; i <= n; i ++){
            if(p[i - 1] == '*') dp[0][i] = true;
            else break;
        }
        for(int i = 1; i <= m; i ++){
            for(int j = 1; j <= n; j ++){
                if(p[j - 1] == '*'){
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - 1] || dp[i][j - 1]; //匹配n次或1次或0次
                }else if(s[i - 1] == p[j - 1] || p[j - 1] == '?'){
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};