Leetcode 单词搜索

Question

我目前正在尝试解决 Word Search problem on leetcode。题目如下：

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

我的尝试如下：

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)
            return 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)
        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

现在，如果我要编辑板输入以检查是否访问了某个状态，我就能够解决问题，但我不想修改输入数组，所以我选择使用哈希集来执行此操作。但是我无法正确执行检查，这就是我的代码失败的原因，所以我希望有人能帮助我。谢谢！

Answer 1

对于回溯算法，您必须收回您所做的“移动”。因此，在这种情况下，您必须在进行递归调用后从 seen 中删除 loc。这是一个简单的修复建议：

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 单词搜索

Leetcode Word Search

algorithm

backtracking

data-structures