class Solution {
public:
    bool isMatch(string s, string p) {
        memset(dp,false,sizeof(dp));
        int ns = s.size(),np = p.size();
        bool flag;
        for(int i=1;i<ns;i++){
            dp[i][0] = false;
        }
        dp[0][0] = true;
        for(int i=0;i<np;i++){
            flag = true;
            for(int j=0;j<=i;j++){
                if(p[j]!='*'){
                    flag = false;
                    break;
                }
            }
            if(flag)dp[0][i+1] = true;
            else    dp[0][i+1] = false;
        }
        for(int j=0;j<np;j++){
            if(p[j]=='*'){
                for(int i=0;i<ns;i++){
                    dp[i+1][j+1] = dp[i][j]||dp[i+1][j]||dp[i][j+1];
                }
            }
            else if(p[j]=='?'){
                for(int i=0;i<ns;i++){
                    dp[i+1][j+1] = dp[i][j];
                }
            }
            else{
                for(int i=0;i<ns;i++){
                    if(s[i]==p[j]){
                        dp[i+1][j+1] = dp[i][j];
                    }
                    else{
                        dp[i+1][j+1] = false;
                    }
                }
            }
        }
        // for(int i=0;i<=ns;i++){
        //     for(int j=0;j<=np;j++){
        //         cout<<dp[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        return dp[ns][np];
    }
private:
    int dp[1030][1030];
};