Interleaving Solution using DP and Memoization with O(n^3) time complexity

int a,b,c;
string s1,s2,s3;
int dp[150][150][150];
bool is_good(int i,int j,int k){
if(i==a && j==b) return true;
if(i==a) return s2.substr(j,b-j)==s3.substr(k,c-k);
if(j==b) return s1.substr(i,a-i)==s3.substr(k,c-k);
if(dp[i][j][k]!=-1) return dp[i][j][k];
int i1=i,j1=j,k1=k;
bool ans=false;
while(i1<a && s1[i1]==s3[k1]){
i1++;k1++;
ans|=is_good(i1,j,k1);
}
i1=i;j1=j;k1=k;
while(j1<b && s2[j1]==s3[k1]){
j1++;k1++;
ans|=is_good(i,j1,k1);
}
return dp[i][j][k]=ans;
}
int Solution::isInterleave(string A, string B, string C) {
a=A.length();
b=B.length();
c=C.length();
s1=A;s2=B;s3=C;
if(c!=a+b) return 0;
memset(dp,-1,sizeof(dp));
return is_good(0,0,0);
}

Click here to start solving coding interview questions