Recursion with memo c++


#1

int dp[151][151];

int solve(int i,int j,int k,int x,int y,int z,string a,string b,string c,string curr)
{
if(i==x)
{
if(j<y)
{
curr+=b.substr(j,y);
}
if(curr==c) return true;
return false;
}
if(j==y)
{
if(i<x)
{
curr+=a.substr(i,x);
}
if(curr==c)
{
return true;
}
return false;
}
if(dp[i][j]!=-1) return dp[i][j];
if(a[i]==c[k] || b[j]==c[k])
{
if(a[i]==c[k] and b[j]==c[k])
{
curr+=a[i];
return dp[i][j]=(solve(i+1,j,k+1,x,y,z,a,b,c,curr) or solve(i,j+1,k+1,x,y,z,a,b,c,curr));
}
else if(a[i]==c[k])
{
curr+=a[i];
return dp[i][j]=solve(i+1,j,k+1,x,y,z,a,b,c,curr);
}
else
{
curr+=b[j];
return dp[i][j]=solve(i,j+1,k+1,x,y,z,a,b,c,curr);
}

}
return dp[i][j]=false;
}

int Solution::isInterleave(string A, string B, string C) {
memset(dp,-1,sizeof(dp));

return solve(0,0,0,A.size(),B.size(),C.size(),A,B,C,"");

}