Code Bug Fix: Can someone tell me if this approach to the Longest Common Subsequence of Three Sequences problem is correct

Original Source Link

Is it possible to do Longest Common Subsequence of Three Sequences using the same algorithm used for solving Longest Common Subsequence of Two Sequences,

My idea is that i find the following common subsequences. Suppose that the three sequences are ‘a’,’b’ and ‘c’. So i will pass to the function used to solve Longest Common Subsequence of Two Sequences as 1)(a,b) 2)(b,c) and 3)(c,a) and store the length from each of the three cases in an array and finally output the minimum among the three.

I have been able to make it till the the last test case and I would appreciate if someone can suggest whether the above mentioned idea is correct or not

I have used the table approach to solve Longest Common Subsequence of Two Sequences and it worked for all test cases. (Table method inspiration from this video https://www.youtube.com/watch?v=NnD96abizww)

s1 = [0] + set1
s2 = [0] + set2
s3 = [0] + set3

T = [] #OUTPUT ARRAY
D2 = [] #2D ARRAY 

for k in range(o + 1):
    D2 = []
    for j in  range(m+1):
        x = [0]*(n+1) #THIS IS IMPORTANT ; IF PLACED OUT THEN IT WILL CREATE A REFERENCE
        D2.append(x)
    T.append(D2)

#INITIALLY T IS AN ARRAY OF ZEROS WITH THE RIGHT DIMENSION

for k in range(1,o+1):
    for j in range(1 ,m+1):
        for i  in range(1,n+1):
            if(s1[i] == s2[j] == s3[k]):
                T[k][j][i] = T[k-1][j-1][i-1] + 1
            else:
                x = []
                x.append(T[k][j][i-1])
                x.append(T[k][j-1][i])
                x.append(T[k-1][j][i])
                T[k][j][i] = max(x)

print(T[k][m][n])

Tagged : /

Leave a Reply

Your email address will not be published. Required fields are marked *