# Longest common subsequence solution reconstruction during DP is wrong

I've implemented longest common substring in python. I know the usual way to reconstruct the path. But, I am reading my algorithm many times, I don't understand why it doesn't work for some test-cases. I am trying to construct the solution while the longest path is being made through dynamic programming.

def lcs(s1, s2):
n = len(s1)
m = len(s2)

trow =  * (m+1)
table = [trow] * (n+1)

srow = [""] * (m+1)
solution = [srow] * (n+1)

for i in range(1, n+1):
for j in range(1, m+1):
if s1[i-1] == s2[j-1]:
table[i][j] = table[i-1][j-1] + 1

# Adding this character to the solution
solution[i][j] = solution[i-1][j-1] + s1[i-1]

elif table[i][j-1] > table[i-1][j]:
table[i][j] = table[i][j-1]

# Choosing the solution related to the longer path
solution[i][j] = solution[i][j-1]

else:
table[i][j] = table[i-1][j]

# Choosing the solution related to the longer path
solution[i][j] = solution[i-1][j]

return solution[n-1][m-1]

lcs('amin', 'kahmjiknln')
# Returns 'amin'

lcs('amin', 'aaaakahmjiknln')
# Returns 'aaaaamin'

• Debugging or diagnosing problems with your code is off-topic here. We're not a coding site. Questions about algorithms can be on-topic, but we discourage questions written in code, as not everyone understands Python, and our focus is on the algorithm not on the implementation. – D.W. Feb 28 at 1:31

## 2 Answers

Lets deal with the issues one at a time, since there are a few of them.

## Problem 1

Take a look at those lines of code:

trow =  * (m+1)
table = [trow] * (n+1)

srow = [""] * (m+1)
solution = [srow] * (n+1)


The problem with this code, is that the same list is being placed a few times. This means, that every list in $table$ must be all identical to $trow$ at all times. By changing one of the values in there, it will change all of them. For example, if $m=n=1$, then table == [[0,0],[0,0]]. Now, assume we somehow did this update: table = 9. Then, we will have table == [[0, 9], [0, 9]] since $table$ contains the same list twice. This is essentially caused because lists are just pointers, and thus if you just copy the value in them it will just copy the pointer. A similar behavior can be seen in this code:

a = 5 # a == 5
b = a # a == 5, b == 5
b = 10 # a == 5, b == 10

A = [0, 1] # A == [0, 1]
B = A # A == [0, 1], B == [0, 1], A is B
B = 9 # A == [9, 1], B == [9, 1], A is B


Here, the same thing happened: $$a$$ is not a list and therefore was copied as expected, but $$A$$ is a list and thus only the pointer to it was copied to $$B$$. A change in $$B$$ changed $$A$$ as well.

Back to your question. How to fix it, you ask? Like so:

table = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

solution = [["" for _ in range(m + 1)] for _ in range(n + 1)]


## Problem 2

You have a slight problem with the indices. Since $$solution$$ is an $$(n+1)$$-by-$$(m+1)$$ matrix, you want solution[n][m] instead of solution[n - 1][m - 1]

Programming questions are off-topic here. Anyway your matrices table and solution are not properly initialized as they contain references to the same objects. Try:

    table = [*(m+1) for j in range(n+1)]
solution = [ ["" for i in range(m+1)] for j in range(n+1) ]


Moreover, the returned string should be solution[n][m] and not solution[n-1][m-1].