Lmao, solution works without DP too


#1

//int DP[110][110][110];
bool check(string& A, string& B, string& C , int i,int j,int k)
{

if(k==0)
    return true;
if(i==0 && j==0)
    return false;
//if(DP[i][j][k] != -1)
//    return DP[i][j][k];

bool check1 = false;
bool check2 = false;
if(i>0 && A[i-1] == C[k-1])
    check1 = check(A,B,C,i-1,j,k-1);
if(j>0 && B[j-1] == C[k-1])
    check2 = check(A,B,C,i,j-1,k-1);
//return DP[i][j][k] = check1 || check2;

return check1 || check2;

}
int Solution::isInterleave(string A, string B, string C)
{
//memset(DP,-1,sizeof(DP));
return check(A,B,C,A.length(),B.length(),C.length());
}