LeetCode 79. 存储以前访问过的单词搜索问题

Question

我的问题非常类似于： leetcode 79 word search python solution, need help on debugging

我遇到的问题是一样的：

[["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

Answer 1

我对您的代码的理解是，您正在执行 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。达到时间限制的最简单方法是注意每当我们回溯时，我们不需要存储我们访问的瓦片的顺序；我们只需要知道要从我们的 visited 集中删除哪个图块。这意味着我们可以使用一组元组而不是列表列表，这使得 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 的执行时间限制。

LeetCode 79. 存储以前访问过的单词搜索问题

LeetCode 79. Word Search problems storing previously visited

python

algorithm

recursion