好的，我们这次来详细讲解 LeetCode 第 79 题「单词搜索」。

1. 题目描述

给定一个 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.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

2. 思路分析

这个问题是典型的二维平面上的回溯（DFS）问题。
核心是：从网格的每一个位置出发，尝试向四个方向（上、下、左、右）搜索，匹配单词的每一个字符。

关键点：

1. 同一个单元格的字母不能重复使用，所以需要标记访问状态，回溯时恢复。
2. 如果当前路径匹配失败，要回溯到上一步，尝试其他方向。
3. 搜索过程中，如果单词全部匹配完成，立即返回成功。

3. 解题步骤详解

3.1 主函数逻辑

1. 遍历网格的每一个位置 (i, j)。
2. 从该位置开始进行 DFS 回溯搜索，查找是否能够匹配单词 word。
3. 如果某个起点开始的搜索返回 true，则最终结果为 true。
4. 如果所有起点都搜索完毕仍未找到，返回 false。

3.2 DFS 回溯函数设计

函数定义：
dfs(i, j, index) 表示当前在网格的 (i, j) 位置，需要匹配 word[index]。

递归终止条件：

• 如果 index == word.length()，说明单词全部匹配成功，返回 true。
• 如果 (i, j) 超出网格范围，返回 false。
• 如果当前单元格的字符不等于 word[index]，返回 false。
• 如果当前单元格已经被访问过，返回 false（通过标记判断）。

递归过程：

1. 标记当前单元格为已访问（例如用特殊字符标记，或使用独立的 visited 数组）。
2. 向四个方向递归搜索：(i+1, j)，(i-1, j)，(i, j+1)，(i, j-1)。
3. 如果任意一个方向返回 true，则返回 true。
4. 否则，回溯：恢复当前单元格的原始字符（或标记为未访问）。
5. 返回 false。

4. 代码实现（Python）

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        
        def dfs(i, j, index):
            # 单词全部匹配成功
            if index == len(word):
                return True
            # 越界检查
            if i < 0 or i >= m or j < 0 or j >= n:
                return False
            # 字符不匹配或已访问
            if board[i][j] != word[index]:
                return False
            
            # 标记为已访问（用特殊字符，避免重复使用）
            temp = board[i][j]
            board[i][j] = '#'  # 标记
            
            # 四个方向搜索
            if (dfs(i+1, j, index+1) or
                dfs(i-1, j, index+1) or
                dfs(i, j+1, index+1) or
                dfs(i, j-1, index+1)):
                return True
            
            # 回溯，恢复字符
            board[i][j] = temp
            return False
        
        # 主循环：尝试每一个起点
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

5. 复杂度分析

• 时间复杂度：最坏情况下，我们需要尝试每个格子作为起点，每个 DFS 深度最多为单词长度 L，且每个节点有 4 个方向（但已访问的不会重复走），所以是 O(m * n * 4^L)。由于 L 最大 15，且 m、n 最大 6，实际可行。
• 空间复杂度：主要是递归栈的深度，最多为单词长度 L，即 O(L)。

6. 关键点总结

1. 回溯标记：用 '#' 临时修改棋盘，回溯时恢复，避免额外 visited 数组。
2. 剪枝：一旦某个方向成功就立即返回，不再尝试其他方向。
3. 递归终止条件顺序：先判断是否匹配完单词，再判断越界和字符匹配，顺序很重要。
4. 小数据范围：m、n 最大 6，允许指数级搜索。

这样一步步分析，你应该能清晰理解「单词搜索」的回溯解法了。