字母迷宫

难度: Medium

字母迷宫游戏初始界面记作 m x n 二维字符串数组 grid，请判断玩家是否能在 grid 中找到目标单词 target。
注意：寻找单词时必须按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母 不允许被重复使用 。

示例 1：

输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "ABCCED"
输出：true

示例 2：

输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "SEE"
输出：true

示例 3：

输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "ABCB"
输出：false

提示：

m == grid.length
n = grid[i].length
1 <= m, n <= 6
1 <= target.length <= 15
grid 和 target 仅由大小写英文字母组成

注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/

Submission

运行时间: 208 ms

内存: 18.4 MB

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True
            board[i][j] = ''
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = word[k]
            return res

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

Explain

此题解采用深度优先搜索（DFS）策略来遍历字母迷宫，并试图在其中寻找目标单词。从迷宫的每一个格子开始，尝试向四个方向（上、下、左、右）扩展搜索，以匹配目标单词的每个字符。搜索过程中使用递归函数dfs(i, j, k)来实现，其中i和j表示当前的行和列位置，k表示目标单词中当前正在匹配的字符索引。如果当前位置越界或字符不匹配，则返回False。如果所有字符都成功匹配（即k等于单词长度减一），则返回True。为了防止在DFS过程中重复使用同一单元格，将当前单元格的值暂时设置为空字符串，并在搜索返回后恢复原值。只要从任意起点开始的DFS返回True，就表示可以在迷宫中找到目标单词。

时间复杂度: O(m*n*4^L)

空间复杂度: O(L)

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            # 检查是否越界或当前字符不匹配
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]:
                return False
            # 检查是否已匹配所有字符
            if k == len(word) - 1:
                return True
            # 标记当前格子为已访问
            board[i][j] = ''
            # 尝试向四个方向搜索
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            # 恢复当前格子的字符
            board[i][j] = word[k]
            return res

        # 从每个格子尝试开始搜索
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                    return True
        return False

Explore

在DFS搜索过程中，为了避免重复访问同一个格子，需要暂时将当前格子标记为已访问。这通常通过修改格子的内容来实现，例如将当前格子的字符暂时设置为空字符串或其他特殊标记。在DFS的每一层递归调用之后，重要的是要将格子恢复到原始状态，以使这个格子可以在其他搜索路径中被重新使用。这种方法确保了每次搜索路径都是独立的，并且棋盘的状态在每次搜索后都会被正确地恢复。

DFS递归调用栈的最大深度主要取决于目标单词的长度。在最坏情况下，如果整个棋盘几乎或完全匹配整个单词，那么递归的深度可能会达到单词的长度。这是因为每递归一次，都会向前匹配单词的下一个字符。棋盘的大小影响的是递归的广度，即从每个格子开始的可能的搜索路径数量，但最大深度仍然由单词长度决定。

深度优先搜索(DFS)在这种类型的问题中被选择，主要是因为它能够快速深入探索可能的单词匹配路径，一旦找到匹配就可以立即返回成功，不需要完全遍历所有路径。相比之下，广度优先搜索(BFS)则会层层扩展，需要更多的内存来存储在每一层搜索中的所有可能状态，而且在找到完整匹配前不会停止。在寻找单一解的问题中，DFS往往更有效率。不过，BFS在找到最短路径问题中更有优势。

是的，在给定的代码实现中，算法会遍历棋盘中的每一个格子作为起始点，并尝试从每个包含单词第一个字符的格子开始执行DFS。这意味着如果单词的第一个字符在棋盘上出现多次，算法会从这些格子中的每一个开始搜索，以尝试找到完整的单词。这样做确保了不会错过任何可能的匹配路径。