LeetCode 79. 单词搜索

字数 1301 2025-10-26 09:00:43

LeetCode 79. 单词搜索

题目描述
给定一个 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 可以拼出单词（注意同一单元格不能重复使用）。

解题过程

问题分析
本题需要在二维网格中寻找一条路径，路径上的字符按顺序连接恰好等于目标单词。由于路径方向不确定（上下左右），且不能重复使用单元格，适合用回溯算法（DFS+状态重置）解决。
核心思路
- 遍历网格的每个单元格，作为搜索的起点。
- 从起点开始进行深度优先搜索（DFS），尝试匹配单词的每个字符。
- 若当前字符匹配，则继续向四个方向（上、下、左、右）搜索下一个字符。
- 如果某个方向最终能匹配完整单词，返回 true；否则回溯（恢复单元格状态，尝试其他方向）。
关键细节
- 避免重复使用：在搜索过程中临时修改已访问的单元格（例如标记为特殊字符如 #），回溯时恢复原始字符。
- 剪枝优化：若当前字符不匹配，立即终止搜索；若已找到完整单词，提前结束所有搜索。
步骤分解
步骤 1：主函数逻辑
- 遍历网格中的每个单元格 (i, j)，调用 DFS 函数，以该单元格为起点尝试匹配单词。
- 若任一起点返回 true，则最终结果为 true。
步骤 2：DFS 函数设计
- 参数：当前坐标 (i, j)，当前匹配到单词的索引 index。
- 终止条件：
  - 若 index == len(word)，说明已匹配完整单词，返回 true。
  - 若当前坐标越界或当前字符不匹配 word[index]，返回 false。
- 标记与探索：
  - 将当前单元格的值临时保存，并标记为已访问（如改为 #）。
  - 向四个方向递归调用 DFS，检查能否匹配剩余字符（index+1）。
  - 若任一方向成功，返回 true；否则回溯：恢复单元格的原始值，返回 false。
步骤 3：方向处理
- 使用方向数组 directions = [(0,1), (0,-1), (1,0), (-1,0)] 简化代码。
- 遍历四个方向，生成新坐标 (ni, nj)，确保新坐标在网格范围内。
复杂度分析
- 时间复杂度：最坏情况下需遍历所有路径（$O(m \cdot n \cdot 4^L)$，其中 $L$ 为单词长度）。
- 空间复杂度：DFS 递归栈深度最大为 $O(L)$。

示例推导
以示例中的 word = "ABCCED" 为例：

从 (0,0) 的 A 开始匹配，匹配成功后标记 A 为 #。
向右找到 B，标记并继续向右找到 C，向下找到 C（注意不能重复使用已标记的单元格）。
继续向下找到 E，向左找到 D，此时匹配完整单词，返回 true。

通过这种回溯方法，可系统性地探索所有可能的路径，同时保证效率。

LeetCode 79. 单词搜索题目描述给定一个 m x n 的二维字符网格 board 和一个字符串单词 word 。需要判断单词 word 是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格（包括水平相邻或垂直相邻）的字母构成。同一个单元格内的字母不允许被重复使用。示例输入：输出： true 解释：路径 A→B→C→C→E→D 可以拼出单词（注意同一单元格不能重复使用）。解题过程问题分析本题需要在二维网格中寻找一条路径，路径上的字符按顺序连接恰好等于目标单词。由于路径方向不确定（上下左右），且不能重复使用单元格，适合用回溯算法（DFS+状态重置）解决。核心思路遍历网格的每个单元格，作为搜索的起点。从起点开始进行深度优先搜索（DFS），尝试匹配单词的每个字符。若当前字符匹配，则继续向四个方向（上、下、左、右）搜索下一个字符。如果某个方向最终能匹配完整单词，返回 true ；否则回溯（恢复单元格状态，尝试其他方向）。关键细节避免重复使用：在搜索过程中临时修改已访问的单元格（例如标记为特殊字符如 # ），回溯时恢复原始字符。剪枝优化：若当前字符不匹配，立即终止搜索；若已找到完整单词，提前结束所有搜索。步骤分解步骤 1：主函数逻辑遍历网格中的每个单元格 (i, j) ，调用 DFS 函数，以该单元格为起点尝试匹配单词。若任一起点返回 true ，则最终结果为 true 。步骤 2：DFS 函数设计参数：当前坐标 (i, j) ，当前匹配到单词的索引 index 。终止条件：若 index == len(word) ，说明已匹配完整单词，返回 true 。若当前坐标越界或当前字符不匹配 word[index] ，返回 false 。标记与探索：将当前单元格的值临时保存，并标记为已访问（如改为 # ）。向四个方向递归调用 DFS，检查能否匹配剩余字符（ index+1 ）。若任一方向成功，返回 true ；否则回溯：恢复单元格的原始值，返回 false 。步骤 3：方向处理使用方向数组 directions = [(0,1), (0,-1), (1,0), (-1,0)] 简化代码。遍历四个方向，生成新坐标 (ni, nj) ，确保新坐标在网格范围内。复杂度分析时间复杂度：最坏情况下需遍历所有路径（$O(m \cdot n \cdot 4^L)$，其中 $L$ 为单词长度）。空间复杂度：DFS 递归栈深度最大为 $O(L)$。示例推导以示例中的 word = "ABCCED" 为例：从 (0,0) 的 A 开始匹配，匹配成功后标记 A 为 # 。向右找到 B ，标记并继续向右找到 C ，向下找到 C （注意不能重复使用已标记的单元格）。继续向下找到 E ，向左找到 D ，此时匹配完整单词，返回 true 。通过这种回溯方法，可系统性地探索所有可能的路径，同时保证效率。