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.
CodePudding user response:
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]