我的问题与以下内容非常相似：leetcode 79字搜索python解决方案，需要帮助调试
我遇到麻烦的情况是一样的：
[["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]
"ABCESEEEFS"
我遇到的问题基本上是一样的。前面提到的问题已经得到了回答，所以我理解了这个问题的原理(如果我删除了之前访问过的关于检查的部分，那么在这种情况下代码就成功了(，但有人能一步一步地解释为什么我的visited列表被污染了吗？
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
我对您的代码的理解是，您正在执行DFS以查找组成单词的瓦片序列。如果这是真的，那么每当您达到无法通过向上递归并从visited中删除该瓦片来形成单词的状态时，您就需要回溯(请记住，该列表在所有对traverse()的递归调用中共享(。
这里有一个解决方案，它将通过您给出的测试用例。
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):
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])
if (
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)
):
return True
else:
visited.pop()
return False
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
然而，此代码将TLE。要达到时间限制，最简单的方法是注意，无论何时回溯，我们都不需要存储我们访问的瓷砖的顺序；我们只需要知道从CCD_ 4集合中删除哪个瓦片。这意味着我们可以使用一组元组而不是列表列表，这使得在visited中查找更快。
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):
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.add((a,b))
if (
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)
):
return True
else:
visited.remove((a, b))
return False
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,set()) == True:
return True
return False
这将超过LeetCode的执行时间限制。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def backtrack(loc: tuple, i: int) -> bool:
x = loc[0]
y = loc[1]
if loc in seen:
return False
if x >= len(board) or y >= len(board[0]):
return False
if 0 > x or 0 > y:
return False
if board[x][y] != word[i]:
return False
if i >= len(word)- 1:
return True
seen.add(loc)
res = backtrack((x+1, y), i+1) or backtrack((x-1, y), i+1) or backtrack((x, y-1), i+1) or backtrack((x,y+1), i+1)
seen.remove(loc) # Removes loc from seen
return res
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == word[0]:
seen = set()
if backtrack((i, j), 0):
return True
return False
在Leetcode尝试使用Python3格式的代码，您将通过…