79. 单词搜索

题目链接（中等）

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中「相邻」单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

数据范围：

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

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

示例

示例 1：

输入： board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出： true

示例 2：

输入： board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
输出： true

示例 3：

输入： board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
输出： false

方法一：回溯

思路及解法

从网格的每一个格子出发，尝试匹配 word 的每一个字符。

定义 check(i, j, k) 表示：从 (i, j) 出发，能否匹配 word 从第 k 个字符开始的后缀 word[k..]。

执行步骤：

1. 如果 board[i][j] != word[k]，当前字符不匹配，直接返回 False；
2. 如果 k == len(word) - 1，说明已经匹配到最后一个字符，返回 True；
3. 否则，把 (i, j) 加入 visited，遍历四个相邻位置：
   • 越界、已访问的跳过；
   • 对每个合法邻居递归 check(ni, nj, k+1)，只要有一个返回 True，就整体返回 True；
4. 递归返回前把 (i, j) 从 visited 中移除（撤销选择）。

外层枚举每个起点 (i, j)，调用 check(i, j, 0)，只要有一个成功就返回 True。

直觉理解：在网格上做 DFS 搜索一条路径，路径要能依次匹配 word 的字符。visited 保证同一个格子不会被重复使用，搜索失败后要「退回来」换其他方向。

代码

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        m, n = len(board), len(board[0])
        visited = set()

        def check(i: int, j: int, k: int) -> bool:
            if board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True

            visited.add((i, j))
            result = False
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in visited:
                    if check(ni, nj, k + 1):
                        result = True
                        break
            visited.remove((i, j))
            return result
            
        for i in range(m):
            for j in range(n):
                if check(i, j, 0):
                    return True
        return False

复杂度分析

• 时间复杂度：一个非常宽松的上界为 $O(MN \cdot 3^L)$，其中 $M, N$ 是网格的长宽，$L$ 是 word 的长度。首次调用可以进入 4 个分支，其余每次最多 3 个分支（不能走回头路），所以 check(i, j, 0) 的时间是 $O(3^L)$，外层共 $O(MN)$ 次。实际由于剪枝，远小于这个上界。
• 空间复杂度：$O(MN)$，visited 集合最多存储 $MN$ 个元素，递归栈深度最大为 $O(\min(L, MN))$。

方法二：原地标记（省去 visited 集合）

思路及解法

可以不用额外的 visited 集合，直接把访问过的格子改成 '#'（或任意不属于字母表的字符），递归返回时再改回来。这样每次判断只需要检查 board[i][j] 是否为 '#'，省去集合的内存与哈希开销。

代码

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        m, n = len(board), len(board[0])

        def check(i: int, j: int, k: int) -> bool:
            if board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True

            temp = board[i][j]
            board[i][j] = '#'      # 标记为已访问
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':
                    if check(ni, nj, k + 1):
                        board[i][j] = temp     # 注意：找到后也要还原
                        return True
            board[i][j] = temp      # 撤销标记
            return False

        for i in range(m):
            for j in range(n):
                if check(i, j, 0):
                    return True
        return False

注意：找到答案提前返回时，也要先把 board[i][j] 恢复成 temp，否则会修改输入。

复杂度分析

• 时间复杂度：与方法一相同，$O(MN \cdot 3^L)$ 的上界。
• 空间复杂度：$O(L)$，只需递归栈的空间，不再需要额外的 visited 集合。