Easy cpp code using lcs


#1

int getlcs(string A,string B)
{
int m=A.length();
int n=B.length();
int dp[m+1][n+1];
int i,j;
for(i=0;i<=m;i++)
{
for(j=0;j<=n;j++)
{
if(i==0 || j==0)
dp[i][j]=0;
}
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(A[i-1]==B[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
int Solution::isInterleave(string A, string B, string C) {
int m=A.length();
int n=B.length();
int k=C.length();
int i,j;
int l1=getlcs(A,C);
int l2=getlcs(B,C);
if(l1==m && l2==n)
return 1;
else
return 0;
}


#2

for this input why output is 1??
A : “ADEG”
B : “BCDEGH”
C : “ABCDEGH”
It should be zero??


#3

Output is 1 . Because within C both A and B are present . I think that is the concept of interleaving . You take every example, the above condition will satisfy


#4

No, concept of interleave is that you have to use all element of A string as well as B string and make C string without interchanging the actual order of A and B.
Formally size(A) +size(B) = size(C)
check this on wiki.


#5

Wiki is asking money…


#6

Ha to bol de 100 per hour.