2
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – justanothertechdude Jun 23 at 23:57
4
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.