0

我正在尝试使用 python 解决leetcode 79. 单词搜索，但是在调试我的解决方案时遇到了一些麻烦。坚持测试用例：{[["A","B","C","E"],["S","F","E","S"],["A","D ","E","E"]] "ABCESEEEFS"}，它不会通过上面的测试用例，需要一些帮助，谢谢。

class Solution(object):
def exist(self, board, word):
    """
    :type board: List[List[str]]
    :type word: str
    :rtype: bool
    """

    def dfs(board, word, used, x, y):
        if not word: return True

        direction = [[0, 1],[0, -1],[1, 0],[-1, 0]]

        if (0 <= x < len(board)) and (0 <= y < len(board[0])) and ((x, y) not in used) and (board[x][y] == word[0]):

            used.add((x, y))                
            return (dfs(board, word[1:], used, x + direction[0][0], y + direction[0][1]) or 
                    dfs(board, word[1:], used, x + direction[1][0], y + direction[1][1]) or 
                    dfs(board, word[1:], used, x + direction[2][0], y + direction[2][1]) or 
                    dfs(board, word[1:], used, x + direction[3][0], y + direction[3][1]))

        return False



    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(board, word, set(), i, j) == True: return True

    return False
4

1 回答 1

0

您的问题是，当您传入usedrecursive时dfs，实际上是传递了对该函数的引用。也就是说，当您从 开始(0,0)，然后转到(0,1)，依此类推时，您可能已经消费(1,1)了仅在序列后面出现的。

换句话说，used将在您预期的搜索之前很久就包含所有板单元。

要解决此问题，请创建一个克隆used并传递给 recursive dfs：

for dx,dy in direction:
    used_copy = set(used)
    used_copy.add((x,y))
    if dfs(board, word[1:], used_copy, x + dx, y + dy):
        return True
return False

您还可以(x,y)在每次递归dfs调用后删除，这样就不会破坏内存：

used.add((x,y))
for dx,dy in direction:
    if dfs(board, word[1:], used, x + dx, y + dy):
        return True

used.remove((x,y))
return False
于 2018-12-11T21:21:29.523 回答