好的，我们这次来详细讲解 LeetCode 第 79 题：单词搜索（Word Search）。

这道题是回溯算法的经典应用，非常考验对深度优先搜索（DFS）和状态重置的理解。

第一步：题目描述

题目

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

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

示例

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

解释：路径 A -> B -> C -> C -> E -> D 存在，因此返回 true。

注意

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

第二步：问题分析与直觉

我们要在一个二维网格中寻找一个单词，规则是：

1. 从网格的任意一个格子出发。
2. 每一步可以向上、下、左、右四个方向移动一格。
3. 已经走过的格子不能重复走（不能回头）。
4. 走过的路径连起来的字符要恰好等于目标单词 word。

这听起来很像一个“走迷宫”问题。我们需要尝试所有可能的起点，然后从每个起点出发，尝试所有可能的路径，直到找到一条能匹配完整单词的路径。

核心挑战：如何高效地探索所有路径，并在走不通时及时回头（回溯），避免无效搜索？

直觉解法：回溯算法（Backtracking），其本质是深度优先搜索（DFS），但加上了“状态重置”的步骤。

第三步：回溯算法思路详解

我们来一步步拆解回溯算法的设计。

1. 主函数（入口点）

由于单词可以从网格中的任何一个格子开始，我们的主函数需要遍历整个网格，以每个格子作为起点，尝试开始搜索。

• 如果从某个起点出发的搜索找到了单词，立即返回 true。
• 如果所有起点都尝试过了都没找到，返回 false。

2. 回溯搜索函数（核心）

我们定义一个递归函数 dfs(i, j, index)：

• i, j：当前在网格中的坐标。
• index：当前需要匹配的单词 word 中的第几个字符（从 0 开始）。

函数的职责：判断从当前格子 (i, j) 开始，能否匹配到 word 中从 index 位置开始的后缀。

3. 回溯的步骤（递归三部曲）

步骤一：判断递归终止条件（是否成功/失败）

1. 成功条件：index 已经等于 word.length。这意味着我们已经匹配了单词的所有字符，成功找到单词，返回 true。
2. 越界条件：当前坐标 (i, j) 超出了网格范围，说明此路不通，返回 false。
3. 字符不匹配条件：当前网格的字符 board[i][j] 不等于 word[index]，说明这条路从一开始就走不通，返回 false。
4. 重复访问条件：当前格子已经被当前路径使用过了，不能重复使用。我们需要一个机制来标记已经访问过的格子。

步骤二：标记当前状态
在递归进入下一层之前，我们需要标记当前格子已被访问，防止在接下来的深层递归中重复访问这个格子。常用的方法是：

• 将 board[i][j] 修改为一个特殊字符（如 ‘#’），表示“已访问”。
• 这样做的好处是无需额外空间，直接修改原数组，但递归结束后必须恢复。

步骤三：进行递归探索（尝试所有可能性）
在当前格子的上下左右四个方向进行递归搜索。搜索的目标是匹配单词的下一个字符 (index + 1)。

• 只要四个方向中有任意一个返回 true，说明找到了一条可行路径，整个搜索就可以提前结束，返回 true。

步骤四：恢复状态（回溯）
在从当前格子开始的所有可能性都尝试完毕之后，必须将当前格子恢复原状（即把 ‘#’ 改回原来的字母）。

• 为什么？ 因为当前递归调用结束后，会返回到上一层调用（比如从当前格子的上方探索失败，返回到当前格子，然后要去探索右方）。此时对于“探索右方”这个新的分支来说，当前格子应该是未被访问的状态。如果不恢复，路径就被错误地阻塞了。

第四步：代码实现与逐行分析

根据以上思路，我们可以写出如下代码：

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 获取网格的行数 m 和列数 n
        m, n = len(board), len(board[0])
        
        # 定义回溯函数，i, j 是当前坐标，index 是当前要匹配的字符在 word 中的索引
        def dfs(i, j, index):
            # 步骤一：判断终止条件
            # 1. 成功条件：已匹配完单词所有字符
            if index == len(word):
                return True
            # 2. 越界条件：坐标超出网格范围
            if i < 0 or i >= m or j < 0 or j >= n:
                return False
            # 3. 不匹配或已访问条件：当前格子字符不等于目标字符，或已被访问（标记为'#'）
            if board[i][j] != word[index]:
                return False
            
            # 步骤二：标记当前状态（避免重复访问）
            # 将当前格子的字符暂时修改，表示已访问
            temp = board[i][j]
            board[i][j] = '#'
            
            # 步骤三：递归探索四个方向
            # 定义四个方向：上、右、下、左
            directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
            found = False
            for dx, dy in directions:
                # 计算下一个坐标
                new_i, new_j = i + dx, j + dy
                # 递归调用，匹配下一个字符 (index+1)
                # 使用 found 来记录四个方向中是否有任一方向成功
                if dfs(new_i, new_j, index + 1):
                    found = True
                    break # 如果找到一个成功路径，提前终止循环
            
            # 步骤四：恢复状态（回溯）
            # 在返回之前，将当前格子恢复原状，以便其他路径使用
            board[i][j] = temp
            
            # 返回当前搜索的结果
            return found
        
        # 主循环：遍历网格中的每一个格子，以其为起点开始搜索
        for i in range(m):
            for j in range(n):
                # 如果以 (i, j) 为起点搜索成功，则整个函数返回 true
                if dfs(i, j, 0):
                    return True
        # 所有起点都尝试过后仍未找到，返回 false
        return False

第五步：通过示例进行推演

让我们用开头的例子来手动推演一下，加深理解。

输入:
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):
   • 标记 board[0][0] 为 ‘#’。
   • 尝试四个方向：右 (0,1) 是 ‘B’，匹配 word[1]。
3. 进入 dfs(0, 1, 1):
   • 标记 board[0][1] 为 ‘#’。
   • 尝试四个方向：右 (0,2) 是 ‘C’，匹配 word[2]。
4. 进入 dfs(0, 2, 2):
   • 标记 board[0][2] 为 ‘#’。
   • 尝试四个方向：右 (0,3) 是 ‘E’，不匹配 word[3]‘C’；下 (1,2) 是 ‘C’，匹配 word[3]。
5. 进入 dfs(1, 2, 3):
   • 标记 board[1][2] 为 ‘#’。
   • 尝试四个方向：下 (2,2) 是 ‘E’，匹配 word[4]。
6. 进入 dfs(2, 2, 4):
   • 标记 board[2][2] 为 ‘#’。
   • 尝试四个方向：左 (2,1) 是 ‘D’，匹配 word[5]。
7. 进入 dfs(2, 1, 5):
   • 成功条件：index (5) 等于 word.length (6)？不，word 是 "ABCCED"，长度是6，index=5 是最后一个字符 ‘D’。我们需要匹配下一个字符，即 index=6。
   • 在 dfs(2,1,5) 中，先检查 board[2][1] 是否等于 word[5]（即 ‘D’），相等。
   • 然后标记该格子。
   • 接着递归调用 dfs(?, ?, 6)。
   • 在 dfs(?, ?, 6) 中，第一步判断：index == len(word) (6==6) 成立！直接返回 True。
   • 这个 True 被一层层返回，最终主函数得到 True。

关键点观察：在最后一步，index 达到单词长度时，意味着我们已经找到了所有需要的字母，无需再检查网格，直接返回成功。这就是递归的基准情况。

第六步：复杂度分析

• 时间复杂度：最坏情况下，我们需要遍历整个网格的每个单元格作为起点（M*N）。对于每个起点，回溯算法在最坏情况下需要探索所有可能的路径（长度为 L 的单词，每个点有4个方向，但由于不能重复，大约是 3^(L) 种可能，因为除了起点，每个点最多有3个新方向）。因此，最坏时间复杂度为 O(M * N * 3^L)。
• 空间复杂度：主要取决于递归调用栈的深度，深度最大为单词长度 L。因此，空间复杂度为 O(L)。

第七步：总结与升华

单词搜索（Word Search） 是回溯算法的标准例题，它完美展示了回溯的核心思想：

1. 选择：从当前格子选择上下左右四个方向之一前进。
2. 约束：不能出界、不能重复访问、字符必须匹配。
3. 目标：匹配完整单词。
4. 回溯：无论成功失败，在返回前都要撤销当前选择（恢复被标记的格子），以便进行下一个选择。

技巧点睛：

• 状态标记与恢复：通过修改原数组来标记访问状态，是节省空间的常用技巧。务必记得恢复。
• 终止条件顺序：先判断成功（index == len(word)），再判断失败条件（越界、不匹配），逻辑更清晰。
• 剪枝：一旦某个方向找到答案，立即返回，避免不必要的搜索。

希望你通过这个循序渐进的讲解，能完全掌握这道题的精髓！如果还有任何疑问，我们可以再深入探讨。