Length of the longest common sub sequence bottom up

Could I get some feedback on this code? I included a test case as well.

This code computes the longest common sub sequence given paired data, it was not part of any challenge I just did it to learn about dp.

To my understanding it runs in $$\\mathcal{O}(m*v)\$$ where $$\m\$$ is length str1 and $$\v\$$ len str2.

def lcs(word1, word2):

x = len(word1)
y = len(word2)
return _lcs(word1, word2, x, y)

def _lcs(word1, word2, x, y):

matrix = [[-1]*(x) for val in range (0,y)]

for i in range(0, y):
for j in range(0, x):

if word1[j] == word2[i]:
if i-1 < 0 or j-1 < 0:
matrix[i][j] = 1
else:
matrix[i][j] = 1 + matrix[i-1][j-1]

else:
val1 = 0
val2 = 0
if i-1 >= 0:
val1 = matrix[i-1][j]
if j-1 >= 0:
val2 = matrix[i][j-1]
matrix[i][j] = max(val1,val2)

return matrix[y-1][x-1]

a = 'ABC'
b = 'ABCD'
print(lcs(a,b))

• Hi Alex, I updated the main post, its not a challenge qn just one I did to learn something new, I would like feedback on code style/clarity/efficiency. – justanothertechdude Jun 23 '19 at 23:57

x and y are terrible variable names. length1 and length2 would be better.

matrix = [[-1]*(x) for val in range (0,y)]


You are not using val in this list comprehension. Convention is to use _ for throw-away, variables needed for syntax reasons, but not actually used.

0 is the default minimum in range() statements. If you loop from 0 to some limit, you don't need to mention the 0; you can just use range(y).

You are never reading the -1 value anywhere. The value is always overwritten by another value before it is read. To make this clearer, store None instead of -1 in the matrix you are creating.

matrix = [ [None] * x  for _ in range(y) ]


Using i-1 < 0 is an awkward way of writing i == 0. Similarly, i-1 >= 0 can be written simply as i > 0, or perhaps even i, since non-zero values are "Truthy".

The following is awkward and hard to understand. 6 statements, 4 assignments, two conditionals. What does it do? What does it mean?

    val1 = 0
val2 = 0
if i-1 >= 0:
val1 = matrix[i-1][j]
if j-1 >= 0:
val2 = matrix[i][j-1]


Python has a x if cond else y trinary operator, which may help simplify and clarify the code.

    val1 = matrix[i-1][j] if i > 0 else 0
val2 = matrix[i][j-1] if j > 0 else 0


That a lot more concise. Two statements which look the similar; the differences should be clear, and it should be easier to understand what those differences mean.

  for i in range(y):
for j in range(x):

if word1[j] == word2[i]:
matrix[i][j] = 1
if i > 0 and j > 0:
maxtrix[i][j] += matrix[i-1][j-1]

else:
val1 = matrix[i-1][j] if i > 0 else 0
val2 = matrix[i][j-1] if j > 0 else 0
matrix[i][j] = max(val1, val2)


The statement return matrix[y-1][x-1] returns the last column of the last row. You don't actually need to know the dimensions of the matrix for this. Simply return matrix[-1][-1].

After you generate row 1, you no longer need row 0 of the matrix. After you generate row 2, you no longer need row 1 of the matrix. After you generate row 3, you no longer need row 2 of the matrix. This means you could solve the problem in $$\O(m)\$$ memory, instead of $$\O(m*v)\$$ memory, by simply maintaining a prev_row and next_row, instead of an entire matrix.

• Thank you so much, I learn a lot of new stuff. – justanothertechdude Jun 24 '19 at 16:19