79. 单词搜索 (Medium)
专题归类： 08-回溯算法 · 07-图论 LeetCode 链接： https://leetcode.cn/problems/word-search/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中”相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许重复使用。
示例 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
提示：
m == board.lengthn == board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成
题目详细分析
数据范围含义：
m, n <= 6：网格最多 36 个格子，每个格子作为起点尝试 DFS，总搜索空间可控。word.length <= 15：单词长度不超过 15，DFS 深度可控，但最坏分支为 4^15 约 10 亿，所以剪枝至关重要。- 包含大小写字母：board 中的字母区分大小写。
隐藏条件：
- 同一个单元格不能重复使用，意味着需要 visited 标记（或类似机制）。
- 只要找到一条路径即可返回 true，不需要找所有路径——这是优化剪枝的关键（找到就提前终止）。
- 匹配必须严格按顺序，不能跳过或重排字母。
边界条件：
- word 长度可能大于网格中所有字母的数量，此时直接返回 false。
- board 只有一个格子且 word 只有一个字母时直接比较。
- 所有格子都可能作为起点。
小白版直白理解
就像在”找字母”游戏中，给你一张写满字母的格子纸和一个单词，你要从某个格子出发，上下左右移动（不能走对角线），踩过的格子上的字母连起来正好是那个单词。走过的格子不能再走第二次（不然就犯规了）。
比如找”ABCCED”：先找到 A，然后往右找到 B，再往右找到 C，再往下找 C，再往左找 E，再往下找 D——ABCD的顺序连起来就是 ABCCED。如果中间走错路了，就退回一步换方向试。
解题思路
思路一：DFS 回溯 + 原地图标记（推荐）
核心思想： 从每个格子出发，进行深度优先搜索（DFS）。用 # 临时覆盖格子值来标记已访问（省去 visited 数组），回溯时恢复。
搜索路径可视化（以 board=[[“A”,“B”,“C”],[“S”,“F”,“C”],[“A”,“D”,“E”] ], word=“ABC” 为例）：
起点 (0,0)=A → 匹配 'A'
├→ 右 (0,1)=B → 匹配 'AB'
│ ├→ 右 (0,2)=C → 匹配 'ABC' ✓ 找到！
│ ├→ 左 (0,0)=# (已访问) ✗
│ ├→ 下 (1,1)=F → 'ABF' ✗
│ └→ 上 越界 ✗
├→ 下 (1,0)=S → 'AS' ✗
├→ 左 越界 ✗
└→ 上 越界 ✗
def exist(board, word):
m, n = len(board), len(board[0])
# 早期剪枝：总字母数不够直接返回 False
if len(word) > m * n:
return False
def dfs(i, j, k):
# 已经匹配完所有字符
if k == len(word):
return True
# 越界或不匹配
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
return False
# 标记已访问（用特殊字符覆盖）
temp, board[i][j] = board[i][j], '#'
# 四个方向搜索
found = (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] = temp
return found
# 从每个格子开始尝试
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False思路二：DFS + visited 数组
核心思想： 使用一个二维 visited 数组代替原地图标记，思路完全一致，但多 O(mn) 空间。
def exist(board, word):
m, n = len(board), len(board[0])
visited = [[False] * n for _ in range(m)]
def dfs(i, j, k):
if k == len(word):
return True
if (i < 0 or i >= m or j < 0 or j >= n or
visited[i][j] or board[i][j] != word[k]):
return False
visited[i][j] = True
found = (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))
visited[i][j] = False
return found
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False时间复杂度： O(m x n x 3^L)，L 为单词长度（第一个方向确定后剩下 3 个方向，不走回头路）。 空间复杂度： O(L)，递归栈深度。
易错点
- 忘记回溯还原：标记 visited 后必须在返回前恢复，否则其他起点无法使用该格子。这是网格回溯最常见的问题。
- 四方向顺序优化：先搜索最可能的方向（虽然没有通用规则），但短路或
or天然带剪枝——找到一个就返回。 - 索引越界检查顺序：必须先检查越界再访问 board。写成
board[i][j] != word[k] or 越界会先下标越界报错。 - 早期剪枝遗漏：如果 word 长度 > m x n，直接返回 false。这是简单有效的早期剪枝。
- Python 字符串不可变性：
board[i][j] = '#'直接修改原列表是允许的（列表可变的），但要确保恢复。
框架提炼
网格 DFS 回溯模板：
def dfs(i, j, 状态参数):
if 达到目标状态:
return True
if 越界 or 不匹配 or 已访问:
return False
标记已访问
for each 方向 in [上, 下, 左, 右]:
if dfs(新坐标, 新状态):
return True # 找到即返回
恢复标记
return False与标准回溯的区别：
- 选择不是显式的”遍历选择列表”，而是”尝试四个方向”。
- visited 标记针对的是网格坐标而非元素索引。
- 因为只需要找一条路径，短路返回（found 用 or 连接）可大幅减少搜索量。
优化技巧：
- 反方向剪枝：在上一步方向的反方向上，board 一定是被标记的 visited，实际分支最多 3 个。
- 词频剪枝：如果 word 中某个字母在 board 中出现次数不足，提前返回 false。
关联题目
- 200-岛屿数量 — 网格 DFS 的基础题，但不需要回溯（只需要遍历，不需要撤销标记），对比学习”需要回溯 vs 不需要回溯”的场景。
- 51-N皇后 — 同样是回溯 + 棋盘，N 皇后是逐行放置，单词搜索是逐格匹配。
- 212-单词搜索II — 本题的进阶版：用 Trie 树优化多个单词的搜索，避免重复遍历。
- 46-全排列 — 核心回溯思想一致：做选择→递归→撤销选择，只是选择形式不同（排列是选数字，搜索是走方向）。