Python Solution using LCS


#1

def lcs(x,y):
a=len(x)
b=len(y)
mat=[]
for i in range(a+1):
mat.append([])
for j in range(b+1):
mat[i].append([0,’’])
for i in range(a+1):
for j in range(b+1):
if i==0 or j==0:
mat[i][j]=[0,’’]
elif x[i-1]==y[j-1]:
mat[i][j][0]=mat[i-1][j-1][0]+1
mat[i][j][1]=mat[i-1][j-1][1]+x[i-1]

        else:
            if mat[i-1][j][0]>mat[i][j-1][0]:
                mat[i][j][0]=mat[i-1][j][0]
                mat[i][j][1]=mat[i-1][j][1]
            else:
                mat[i][j][0]=mat[i][j-1][0]
                mat[i][j][1]=mat[i][j-1][1]
return mat[a][b][1]

class Solution:
# @param A : string
# @param B : string
# @param C : string
# @return an integer
def isInterleave(self, A, B, C):
if lcs(A,C)==A and lcs(B,C)==B:
return 1
return 0