'LeetCode 79. Word Search problems storing previously visited
My question is very similar to: leetcode 79 word search python solution, need help on debugging
The case that I'm having trouble with is the same:
[["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]
"ABCESEEEFS"
The problem I'm having is basically the same. The aforementioned question is answered, so I understand the principle idea of the problem (if I delete the part about checking previously visited, the code succeeds for this case), but can somebody explain step by step why my visited list is getting polluted?
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
top = -1
bottom = len(board)
rowstart = -1
rowend = len(board[0])
def traverse(a, b, index, visited):
print(a,b)
print(visited)
print()
if index == len(word):
return True
if a == top or a == bottom or b == rowstart or b == rowend:
return False
if board[a][b] != word[index]:
return False
if [a,b] in visited:
return False
visited.append([a,b])
return (
traverse(a+1, b, index+1, visited)
or
traverse(a, b+1, index+1, visited)
or
traverse(a-1, b, index+1, visited)
or
traverse(a, b-1, index+1, visited)
)
for c in range(0, len(board)):
for d in range(0, len(board[0])):
if board[c][d] == word[0]:
if traverse(c,d,0,[]) == True:
return True
return False
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
