Getting TLE Top Down


#1
int solve(const string& a, int n,const string& b, int m, vector<vector<bool>>&dp){
if(n==0 && m==0)return dp[n][m]=1;
else if((m==0&& n!=0)) return dp[n][m]=0;
else if(n==0){
    if(b[m-1]!='*')return dp[n][m]=0;
    else{
        if(m>1)return dp[n][m]=solve(a,n,b,m-1,dp);
        else return dp[n][m]=1;
    }
}
if(dp[n][m]!=0)return dp[n][m];
if(a[n-1]==b[m-1] || b[m-1]=='?'){
    dp[n][m]=solve(a, n-1, b, m-1, dp);
}else{
    if(b[m-1]=='*'){
        dp[n][m]=max(solve(a,n,b,m-1,dp),max(solve(a,n-1, b,m,dp), solve(a,n-1,b,m-1,dp)));
    }else dp[n][m]=0;
}
return dp[n][m];
}

int Solution::isMatch(const string A, const string B) {
int n=A.size(), m=B.size();
//char x='?', y='*';
vector<vector<bool>>dp(n+1, vector<bool>(m+1,false));
return solve(A, n, B, m, dp);
dp.clear(); 
   // if(ans==0)return 0;
   // else return ans;
}

#2

actaually when you take bool as datatypes in vector so what happen you intislize it with false now what will happen suppose in same case you get false and you stored in your dp vector but when same case again your code doesn’t allow to return false value so you will find again so better is use int datatype so if we false appeared store it 0 and return when -1 is not found


#3

yaa, it is bcoz of recursive-implementation , that’s why only it is suggested that always implement “dp”-solution iteratively.