Two Identical Tables Yields Different DP results

December 29, 2021

I was solving a Hackerrank problem that is just a plain implementation of Longest Common Subsequence

tbl = [[0]*(len(s2)+1)] * (len(s1)+1)

# iterate the two strings and update the [i][j] location accordingly
for i in range(len(s1)+1):
    for j in range(len(s2)+1):
        if i == 0 or j == 0: continue # outer row/col indices
        elif s1[i-1] == s2[j-1]:
            tbl[i][j] = tbl[i-1][j-1] + 1
        else:
            tbl[i][j] = max(tbl[i-1][j], tbl[i][j-1])
            
return tbl[len(s1)][len(s2)]

This kept giving me the wrong answers, even though I know I was implementing the algorithm correctly.

On a whim, I then decided to try initializing my table differently. I found the following 2D array initialization:

[[0]*(len(s2)+1) for i in range(len(s1)+1)]

The only difference is instead of multiplying the outer brackets by len(s)+1, I do the row expansion via a for loop.

Pressing submit, and voila, it accepts the answer.

Curious, I tossed the two tbl initializations in the python console.

>>> x = [[0]*(len(s2)+1)] * (len(s1)+1)
>>> y = [[0]*(len(s2)+1) for i in range(len(s1)+1)]
>>> x == y
True

This is surely strange behavior. Even printing the table contents to the terminal proves identical structure.

>>> for row in x:
...     print(row)
... 
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
>>> for row in y:
...     print(row)
... 
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
[None, None, None, None, None, None, None]
>>>

Does anyone have any idea as to what would be causing this disparity in output? Thinking this maybe had to do with how it was compiling, I tested the function locally with the HR given test case inputs s1 = SHINCHAN; s2 = NOHARAAA, and yielded an incorrect LCS of 6 with my (broken) table init and the correct LCS of 3 with the one I found online.

>Solution :

This is one of the classic Python blunders. You cannot initialize a 2D array using the * operator, like x = [[0]*5]*5. The REASON is that this gives you a list that contains 5 references to the SAME [0,0,0,0,0] list, They aren’t 5 independent lists. If you change x[0][3], you will also change x[1][3] and x[2][3]. Try setting x[2][2] = 9 and y[2][2] = 9 and notice the difference.

>>> x[2][2] = 9
>>> y[2][2] = 9
>>> for row in x:
...     print(row)
...
[0, 0, 9, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 0, 0]
>>> for row in y:
...     print(row)
...
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 9, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]