Question

this python code below is to find the longest common subsequence from two input string !!! however it give me the wrong answer, can any one fix it thanks
def lcs(s1, s2):
    matrix = [["" for x in range(len(s2))] for x in range(len(s1))]
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                if i == 0 or j == 0:
                    matrix[i][j] = s1[i]
                else:
                    matrix[i][j] = matrix[i-1][j-1] + s1[i]
            else:
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1], key=len)

    cs = matrix[-1][-1]

    return len(cs), cs

print(lcs("abcdaf", "acbcf")) 

Answer 1

`Hey,

Note: If you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

There were a lot of logical errors. Also, not len(cs) is nothing since integers don't have len function

Note: Brother sometimes while uploading on HomeworkLib the indentations change. So, I request you to verify it with screenshot once. This is the link where I have saved the code too

https://onlinegdb.com/SJYcRLx8U

def lcs(X , Y):
# find the length of the strings
m = len(X)
n = len(Y)
  
# declaring the array for storing the dp values
L = [[None]*(n+1) for i in range(m+1)]
  
"""Following steps build L[m+1][n+1] in bottom up fashion
Note: L[i][j] contains length of LCS of X[0..i-1]
and Y[0..j-1]"""
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0 :
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1]+1
else:
L[i][j] = max(L[i-1][j] , L[i][j-1])
cs=L[-1][-1];
# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
return L[m][n]
#end of function lcs
  
  
# Driver program to test the above function
X = "abcdaf"
Y = "acbcf"
print(lcs(X, Y))

Kindly revert for any queries

Thanks.