C++ sol | memoization | recursion | n2 complexity


#1

string a,b,c;
int dp[152][152];
bool sol(int i, int j){

if(i==0 && j==0)return true;

if(dp[i][j]!=-1)return dp[i][j];
bool ans = false;

if(i>0 && a[i-1]==c[i+j-1] && b[j-1]!=c[i+j-1]){
    ans |= sol(i-1, j);
}else if(j>0 && b[j-1]==c[i+j-1] && a[i-1]!=c[i+j-1]){
    ans |= sol(i,j-1);
}else if(i>0 && j>0 && a[i-1]==c[i+j-1] && b[j-1]==c[i+j-1]){
    ans |= sol(i-1, j) | sol(i,j-1);
}

return dp[i][j] = ans;

}
int Solution::isInterleave(string A, string B, string C) {
for(int i = 0; i<152; ++i){
for(int j = 0; j<152; ++j){
dp[i][j] = -1;
}
}
a= A, b=B, c=C;
return sol(a.size(),b.size());
}