LeetCode 第 79 题：单词搜索 题目描述 给定一个 m x n 的二维字符网格 board 和一个字符串单词 word。需要判断 word 是否存在于网格中。 单词必须按照字母顺序，通过相邻的单元格（即上下左右相邻）内的字母构成。同一个单元格内的字母在一个单词中不允许被重复使用。 示例 输入：board = [ [ "A","B","C","E"],[ "S","F","C","S"],[ "A","D","E","E"] ], word = "ABCCED" 输出：true 解题思路 这道题的核心是回溯算法（Backtracking）。我们需要在网格中寻找一条路径，使得路径上的字符连起来正好是目标单词。由于路径可以上下左右移动，并且不能重复使用单元格，因此我们需要尝试所有可能的起点，并在每个起点开始进行深度优先搜索（DFS），同时在搜索过程中记录已经访问过的单元格，避免重复使用。 详细步骤 遍历所有起点 我们需要遍历网格中的每一个单元格 (i, j)，将其作为搜索路径的起点。 深度优先搜索（DFS） 对于每一个起点，我们开始一个 DFS 过程。DFS 函数需要接收以下参数： 当前网格中的行索引 i 当前网格中的列索引 j 当前需要匹配的单词字符的索引 index （表示我们已经成功匹配了 word 的前 index 个字符，现在要匹配第 index 个字符） DFS 的终止条件 成功条件 ：如果 index 等于单词 word 的长度，说明我们已经成功匹配了整个单词，返回 true 。 失败条件 ：如果当前单元格 (i, j) 超出了网格的边界，或者当前网格单元格的字符 board[i][j] 不等于单词中第 index 个字符 word[index] ，则当前路径不可能成功，返回 false 。 回溯的核心步骤 标记已访问 ：为了避免在当前的搜索路径中重复使用同一个单元格，在进入 DFS 时，我们需要将当前单元格 board[i][j] 标记为“已访问”。一个常见的做法是将其修改为一个特殊字符（例如 '#' ），或者使用一个额外的等大小布尔数组来记录访问状态。 探索四个方向 ：在当前单元格的字符匹配成功后，我们需要继续探索它的上、下、左、右四个相邻的单元格，看看是否能匹配单词的下一个字符（即 index + 1 ）。只要任意一个方向的探索返回了 true ，就说明我们找到了一条完整路径。 恢复状态（回溯） ：在结束对当前单元格的四个方向的探索后，我们必须将当前单元格的状态恢复原样（例如，将 '#' 改回原来的字符）。这一步至关重要，因为它保证了在尝试其他起点或其他路径时，这个单元格是可用的。 返回最终结果 如果遍历了所有起点，都没有找到一条成功的路径，则最终返回 false 。 举例说明 以示例 board = [ [ "A","B","C","E"],[ "S","F","C","S"],[ "A","D","E","E"] ], word = "ABCCED" 为例。 从 (0,0) 的 'A' 开始，匹配 word[ 0 ]。 匹配成功。标记 (0,0) 为已访问。然后尝试四个方向（比如先向右到 (0,1) 的 'B'），匹配 word[ 1 ]。 匹配成功。标记 (0,1) 为已访问。继续探索 (0,1) 的四个方向（比如先向右到 (0,2) 的 'C'），匹配 word[ 2 ]。 匹配成功。标记 (0,2) 为已访问。继续探索 (0,2) 的四个方向。此时不能向左（(0,1) 已访问），不能向上（越界），不能向下到 (1,2) 的 'C'，匹配 word[ 3 ]。 匹配成功。标记 (1,2) 为已访问。继续探索 (1,2) 的四个方向。向左到 (1,1) 的 'F'，不匹配 word 4 ；向右到 (1,3) 的 'S'，不匹配；向上已访问；向下到 (2,2) 的 'E'，匹配 word 4 。 匹配成功。标记 (2,2) 为已访问。继续探索 (2,2) 的四个方向。向左到 (2,1) 的 'D'，匹配 word 5 。 此时 index 等于单词长度 6，匹配成功，返回 true。在返回的过程中，会逐层回溯，将标记为已访问的单元格恢复原状。 复杂度分析 时间复杂度 ：最坏情况下，我们需要尝试网格中的每一个单元格 (M* N) 作为起点，然后每个起点最多需要进行 4^L 次搜索（L 是单词长度，每个点有 4 个方向，但因为有已访问标记，实际会少很多）。这是一个非常宽松的上界。实际中，通过剪枝（遇到不匹配就返回），效率会高很多。 空间复杂度 ：主要消耗在递归调用栈上，栈的深度最大为单词的长度 L。如果使用额外数组记录访问状态，还需要 O(M* N) 的额外空间。