C++, LCS solution, we just need to check if A&C LCS is A and B&C LCS is B or not


#1

int Solution::isInterleave(string A, string B, string C)
{
// we just need to check if A& C LCS is A and B&C LCS is B or not

int n = A.size() ;
int m = C.size() ;
int t[n+ 1][m+ 1] ;
for( int i = 0; i<n+ 1; i++) t[i][0] = 0 ;
for( int j = 0 ; j<m+ 1; j++) t[0][j] = 0 ;

for( int i= 1; i<n+ 1; i++)
{
    for( int j = 1 ; j<m+ 1; j++)
    {
        if( A[i-1] == C[j-1] ) t[i][j] = 1+ t[i-1][j-1] ;
        else t[i][j] = max(t[i-1][j] , t[i][j-1]) ;
    }
}

int ans1 = t[n][m] ;
if( ans1 != n) return  0;

int w = B.size() ;

int t2[w+ 1][m+ 1] ;
for( int i = 0; i<w+ 1; i++) t2[i][0] = 0 ;
for( int j = 0 ; j<m+ 1; j++) t2[0][j] = 0 ;

for( int i= 1; i<w+ 1; i++)
{
    for( int j = 1 ; j<m+ 1; j++)
    {
        if( B[i-1] == C[j-1] ) t2[i][j] = 1+ t2[i-1][j-1] ;
        else t2[i][j] = max(t2[i-1][j] , t2[i][j-1]) ;
    }
}

int ans2 = t2[w][m] ;
if( ans2 != w) return  0;

return 1; 

}


#2

Poor test cases got you work man, actually you are not checking many cases there may be a case that both are subsequences of the bigger string but there may be more characters present in the bigger string than that of both the smaller strings


#3

this might not work on test case:
QC
PQD
PQCDQ


#4

we can check the length is equal to sum of both and lengths and do this approach


#5

can some one help with Help BUTTON in interviewbit i no idea where its located.