Declare dp as vector<vector<bool>> dp(n,vector<bool>(m,false));

programming
Tags: #<Tag:0x00007f2428e2e5c0>

#1
bool sol(int i,int j,int n,int m,const string &A,const string &B,vector<vector<bool>> &dp,vector<vector<bool>> &ok){
if(j>=m){
    return i>=n;
}
if(i>=n){
    if(B[j]=='*')
        return sol(i,j+1,n,m,A,B,dp,ok);
    else
        return false;
}
bool ans=dp[i][j];
if(ok[i][j]) return ans;
ans=false;

if(A[i]==B[j] || B[j]=='?')
    ans |= sol(i+1,j+1,n,m,A,B,dp,ok);
if(ans==true)  return ans;
if(B[j]=='*'){
    ans |= sol(i,j+1,n,m,A,B,dp,ok);
    if(ans==true)  return ans;
    for(int x=i+1;x<=n;x++){
        ans |= sol(x,j+1,n,m,A,B,dp,ok);
        if(ans==true)  return ans;
    }
}
ok[i][j]=true;
dp[i][j]=ans;
return ans;

}

int Solution::isMatch(const string A, const string B) {
int n=A.length(),m=B.length();
vector<vector> dp(n,vector(m,false));
vector<vector> ok(n,vector(m,false));
return sol(0,0,n,m,A,B,dp,ok)==true;

}