好的，我们来看 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. 思路分析

2.1 问题特点

• 网格中每个位置都可以作为搜索起点。
• 每一步可以向四个方向之一移动，但不能走回头路（不能重复使用单元格）。
• 一旦找到一条路径与单词完全匹配，就返回 true；如果所有路径都尝试后仍不匹配，返回 false。

2.2 核心思路

这明显是一个回溯（Backtracking）问题，类似深度优先搜索（DFS），但需要记录访问过的位置，并在回溯时恢复状态。

步骤：

1. 遍历网格的每个位置 (i, j) 作为起点。
2. 从起点开始 DFS，匹配单词的第 0 个字符。
3. DFS 过程中：
   • 如果当前位置越界，或当前字符不匹配，或已经访问过，则返回失败。
   • 标记当前位置为已访问。
   • 向四个方向递归搜索下一个字符。
   • 回溯：恢复当前位置为未访问。
4. 如果某个方向递归返回 true，则立即返回 true。
5. 所有起点和路径都尝试后仍未找到，返回 false。

3. 详细步骤

3.1 定义 DFS 函数

我们定义一个递归函数：
dfs(i, j, k) 表示从 (i, j) 开始，匹配单词 word 从第 k 个字符开始的后缀。

递归终止条件：

• k == len(word)：说明已经匹配完整个单词，返回 true。
• 越界或 board[i][j] != word[k] 或 (i, j) 已访问过：返回 false。

递归过程：

1. 标记 (i, j) 为已访问（例如用 # 临时替换，或用一个 visited 矩阵记录）。
2. 向四个方向 (i+1, j)、(i-1, j)、(i, j+1)、(i, j-1) 分别递归调用 dfs，k+1。
3. 如果某个方向返回 true，则提前返回 true。
4. 回溯：恢复 board[i][j] 为原字符（或标记为未访问）。
5. 如果四个方向都失败，返回 false。

3.2 主函数

• 遍历每个 (i, j)：
  • 如果 dfs(i, j, 0) 返回 true，则返回 true。
• 遍历结束返回 false。

4. 代码实现（思路对应伪代码）

def exist(board, word):
    m, n = len(board), len(board[0])
    
    def dfs(i, j, k):
        # 终止条件1：匹配完成
        if k == len(word):
            return True
        # 终止条件2：越界或不匹配
        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] = '#'  # 防止重复访问
        # 四个方向搜索
        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] = temp
        return res
    
    for i in range(m):
        for j in range(n):
            if dfs(i, j, 0):
                return True
    return False

5. 复杂度分析

• 时间复杂度：最坏情况下，需要遍历所有路径。
  网格有 m*n 个起点，每个起点 DFS 深度最大为 L（单词长度），每个节点有 4 个方向（但不会走回头路），所以最坏复杂度约为 O(m * n * 4^L)。
  实际由于剪枝（字符不匹配时提前返回），会好很多。
• 空间复杂度：主要是递归栈深度，最大深度为 L，所以是 O(L)。

6. 关键点总结

• 回溯时标记访问与恢复现场必须配对。
• 利用递归返回值提前终止搜索，减少不必要的计算。
• 同一个单元格不能重复使用，所以 DFS 过程中要临时修改棋盘或使用 visited 记录。

这样，我们就完成了「单词搜索」的详细讲解。