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 &lt; 0 or j-1 &lt; 0:
          matrix[i][j] = 1 
        else:
          matrix[i][j] = 1 + matrix[i-1][j-1]

      else:
        val1 = 0
        val2 = 0
        if i-1 &gt;= 0:
          val1 = matrix[i-1][j]
        if j-1 &gt;= 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))
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 &lt; 0 is an awkward way of writing i == 0.  Similarly, i-1 &gt;= 0 can be written simply as i &gt; 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 &gt;= 0:
      val1 = matrix[i-1][j]
    if j-1 &gt;= 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 &gt; 0 else 0
    val2 = matrix[i][j-1] if j &gt; 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 &gt; 0 and j &gt; 0:
          maxtrix[i][j] += matrix[i-1][j-1]

      else:
        val1 = matrix[i-1][j] if i &gt; 0 else 0
        val2 = matrix[i][j-1] if j &gt; 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.