题解 | #通配符匹配#

class Solution {
public:
    /*
        其实一看到这个题目我首先想到的就是动摇规划
        那么就拿动态规划来说
        那么什么是变量
        dp[i][j]代表的是第s[0-i] p[0-j]是否匹配
        选择就是


    */

    bool isMatch(const char *s, const char *p) {
        int size_s = strlen(s);
        int size_p = strlen(p);
        if(size_s==0 && size_p==0) {
            return true;
        }
        if(size_s==0) {
            for(int i=0;i<size_p;i++) {
                if(p[i]!='*') {
                    return false;
                }
            }
            return true;
        }

        // 为了简化初始化
        vector<vector<bool>> dp(size_p+1,vector<bool>(size_s+1,false));
        dp[0][0]=true;

        for(int i=1;i<=size_p;i++) {
            if(p[i-1]!='*') {
                break;
            }
            if(p[i-1]=='*') {
                dp[i][0]=true;
            }
        }

        for(int i=1;i<=size_p;i++) {
            for(int j=1;j<=size_s;j++) {
                if(s[j-1]==p[i-1]) {
                    dp[i][j]=dp[i][j] || dp[i-1][j-1];
                } else if(p[i-1]=='?') {
                    dp[i][j] = dp[i-1][j-1];
                } else if(p[i-1]=='*') {
                    dp[i][j]=dp[i][j] || dp[i][j-1] || dp[i-1][j-1] || dp[i-1][j];
                } else {
                    dp[i][j] = false;
                }

            }
        }

        for(auto a  : dp) {
            for(auto b : a) {
                cout<<b<<" ";
            }
            cout<<endl;
        }
        cout<<endl;
        return dp[size_p][size_s];

    }
};