[Python] Python issue: Two 2D list initialisation methods give different results of a Leetcode...

Question background


I was working on a Leetcode problem 1143. Longest Common Subsequence.

After following a solution, I submitted the code below:

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

# 2D list initialisation Method 1:
# dp = [[0] * (n + 1) ] * (m + 1)

# 2D list initialisation Method 2:
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]


for row in range(1, m + 1):
for col in range(1, n + 1):
if text1[row - 1] == text2[col - 1]:
# Matched! Last top-left diagonal element + 1
dp[row][col] = 1 + dp[row - 1][col - 1]
else:
# Not matched. Whichever is bigger, left or top element
dp[row][col] = max(dp[row - 1][col], dp[row][col - 1])

return dp[m][n]

Unexpected Behaviour


I tried two ways to initialise the 2D list,

# 2D list initialisation Method 1:
dp = [[0] * (n + 1) ] * (m + 1)

# 2D list initialisation Method 2:
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]


but I received different results.

Please see the description below.

Method 1: Using dp = [[0] * (n + 1) ] * (m + 1) to initialise the 2D list


Input 1

text1 = "abcba"
text2 = "abcbcba"


Output 6, Expect 5 (i.e., the correct answer is 5.)

Input 2 -- However, when I swap between two variables

text1 = "abcbcba"
text2 = "abcba"


Output 5 -- which is correct.

Question 1


Why does the same algorithm generate different results with the input in different order?

Method 2: Using dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)] to initialise the 2D list


This method passed all testcases.

Question 2


Why does this way of 2D list initialisation work perfectly but not method 1?

Continue reading...