题解 | #通配符匹配#

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        string S = s;
        string P = p;
        vector<vector<bool>> dp(1001, vector<bool> (1001, false));
        dp[0][0] = true;
        for(int i = 0; i < P.size(); i++) {
            if(P[i] == '*')
                dp[0][i + 1] = true;
            else
                break;
        }
        // 分两种情况
        // 1. s[i]==p[j] || p[j]=='?'，在这种情况下对比前一个字符
        // 2. p[j] == '*'，分两种情况讨论
            // 1、使用'*'：对比s[i-1]和p[j]
            // 2、不使用'*'，即‘*’和空字符形成对应：对比s[i]和p[j-1]，只要两种情况有一种为TRUE，则当前结果为TRUE
        for(int i = 0; i < S.size(); i++) {
            for(int j = 0; j < P.size(); j++) {
                if(S[i] == P[j] || P[j] == '?')
                    dp[i + 1][j + 1] = dp[i][j];
                else if(P[j] == '*')
                    dp[i + 1][j + 1] = dp[i + 1][j] || dp[i][j + 1];
            }
        }
        return dp[S.size()][P.size()];
    }
};