0

Context

For solving a problem Longest Common Subsequence, I wrote a solution that uses Dynamic Programming.

For that, I needed to create a 2D List for storing the elements.

For creating a 2D List, I tried two methods:

  1. Replicating just one element of the list using for loops
  2. Replicating just one element of the list using the * operator
>>> len1 = 3
>>> len2 = 4
>>> [[0]*(len2+1) for i in range(len1+1)]
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

>>> [[0] * (len2+1)] * (len1+1)
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] 

We can see both methods generate lists that are exactly the same, right?

Here's the whole code which contains the actual solution and my solution for solving that problem:

def expected(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])

    # L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
    return L[m][n]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len2 = len(text2)
        len1 = len(text1)

        matrix = [[0] * (len2+1)] * (len1+1)

        for i in range(len1+1):
            for j in range(len2+1):

                if not i or not j:
                    matrix[i][j] = 0

                elif text1[i-1] == text2[j-1]:
                    matrix[i][j] = matrix[i-1][j-1] + 1

                else:
                    matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])

        return matrix[len1][len2]

# Test Cases
strings = [
    ("abcde", "ace"),
    ("abc", "abc"),
    ("abc", "def"),
    ("bsbininm", "jmjkbkjkv"),
    ("abcba", "abcbcba")
]

for text1, text2 in strings:
    # If the solution is right, 
    if (expected(text1, text2) == Solution().longestCommonSubsequence(text1, text2)):
        continue
    print(text1, text2)
    print(
        f"Expected: {expected(text1, text2)} | Actual: {Solution().longestCommonSubsequence(text1, text2)}")
    break
else:
    print("All tests passed!")

The output (python lcs.py):

abcba abcbcba
Expected: 5 | Actual: 6

The Problem

I realised test cases failed with my solution cause of the way I'm creating the nested lists. Even though both methods mentioned above create the same list.

When I replace the line matrix = [[0] * (len2+1)] * (len1+1) in longestCommonSubsequence method with matrix = [[0]*(len2+1) for i in range(len1+1)]

All tests passed!

I do not understand why the method where I use the for loop for generating a nested list passes the test cases but not the one where only where the * operator is used.

Gagan Deep Singh
  • 322
  • 3
  • 11

0 Answers0