好的，我们来看 LeetCode 第 79 题「单词搜索」。

1. 题目描述

给定一个 m x n 的二维字符网格 board 和一个字符串单词 word。
请你判断单词 word 是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格（相邻指上下左右相邻）的字母构成，同一个单元格内的字母不允许被重复使用。

示例

board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED"

返回 true。

2. 思路分析

题目要求在一个二维网格中搜索一个单词，并且路径可以上下左右行走，但不能重复使用同一个格子。
这明显是一个回溯（Backtracking）问题，结合深度优先搜索（DFS）。

核心思路：

1. 遍历网格的每一个格子 (i, j) 作为起点。
2. 从起点开始深度优先搜索，匹配单词的第 1 个字符。
3. 在 DFS 过程中，检查当前格子字符是否匹配单词的当前字符：
   • 如果不匹配，回溯。
   • 如果匹配，标记这个格子为已访问（避免重复使用），然后向四个方向（上、下、左、右）继续 DFS 匹配下一个字符。
4. 如果某个路径能匹配到单词的最后一个字符，说明找到单词，返回 true。
5. 如果所有起点和所有路径都尝试过仍未找到，返回 false。

3. 回溯与 DFS 设计

DFS 函数设计
定义函数 dfs(i, j, k)：

• (i, j) 是当前在网格中的坐标。
• k 是当前要匹配的单词中的字符索引（从 0 开始）。

递归终止条件：

1. 如果 k == len(word)，说明已经匹配完整个单词，返回 true。
2. 如果越界 (i, j) 不在网格内，返回 false。
3. 如果当前格子字符 board[i][j] 不等于 word[k]，返回 false。

标记已访问
为了避免重复使用同一个格子，在进入 DFS 前，将 board[i][j] 修改为一个非字母字符（如 #），表示已访问。
在回溯返回前，恢复 board[i][j] 为原来的字符。

四个方向搜索
从 (i, j) 出发，分别向 (i-1, j)、(i+1, j)、(i, j-1)、(i, j+1) 四个方向递归搜索 dfs(..., k+1)。

4. 代码步骤详解

1. 遍历网格的每个位置 (i, j) 作为起点。
2. 对每个起点调用 DFS，传入 k=0（从单词的第一个字符开始匹配）。
3. 在 DFS 中：
   • 检查是否已经匹配完单词（k == len(word)），是则返回 true。
   • 检查是否越界或字符不匹配，是则返回 false。
   • 标记当前格子为已访问（临时修改为 #）。
   • 向四个方向递归搜索。
   • 回溯：恢复格子字符。
   • 如果四个方向中有任一方向返回 true，则返回 true，否则返回 false。
4. 如果所有起点都试过仍未找到，返回 false。

5. 举例说明

以示例为例：

board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED"

搜索过程（简略）：

1. 起点 (0,0) 字符 'A' 匹配 word[0]。
2. 进入 DFS：
   • 标记 (0,0) 为 #。
   • 尝试四个方向：向右 (0,1) 是 'B'，匹配 word[1]。
   • 继续 DFS：标记 (0,1) 为 #，向右 (0,2) 是 'C'，匹配 word[2]。
   • 继续 DFS：标记 (0,2) 为 #，向右 (0,3) 是 'E'，不匹配 word[3]='C'，回溯。
   • 向下 (1,2) 是 'C'，匹配 word[3]。
   • 继续 DFS：标记 (1,2) 为 #，向下 (2,2) 是 'E'，匹配 word[4]。
   • 继续 DFS：标记 (2,2) 为 #，向左 (2,1) 是 'D'，匹配 word[5]。
   • 此时 k=5 等于单词长度，返回 true。

6. 复杂度分析

• 时间复杂度：最坏情况是遍历整个网格的每个格子作为起点，每个起点 DFS 深度为单词长度 L，四个方向，所以是 O(M * N * 4^L)。
• 空间复杂度：主要是递归栈深度，最多 L 层，所以是 O(L)。

7. 关键点总结

• 回溯时标记已访问并恢复现场是核心。
• 剪枝：一旦某个方向找到答案，立即返回，不需要继续搜索其他方向。
• 注意边界条件（越界判断）。

这样循序渐进地分析，你应该能清晰地理解「单词搜索」这道题的回溯解法了。