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:
- Replicating just one element of the list using
forloops - 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.