【LeetCode 热题 100】79. 单词搜索——回溯
Problem: 79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(M * N * 3^L)
- 空间复杂度：O(L)
整体思路
这段代码旨在解决一个经典的二维网格搜索问题：单词搜索 (Word Search)。其核心功能是判断一个给定的单词 word 是否存在于一个字符网格 board 中。构成单词的路径规则是：字母必须在网格中水平或垂直相邻，并且同一个单元格的字母在路径中不允许被重复使用。
该算法采用了 深度优先搜索（DFS） 结合 回溯（Backtracking） 的策略。其整体思路可以分解为以下几个步骤：
-
主驱动逻辑（遍历所有起点）：
exist方法是算法的入口。它通过两层嵌套的for循环遍历网格board中的每一个单元格(i, j)。- 这个遍历的目的是将每一个单元格都视作单词
word的一个潜在 起始点。 - 对于每一个起点，它都会调用核心的
dfs辅助函数来尝试进行深度搜索。如果任何一次dfs调用返回true，意味着找到了完整的单词路径，程序立即返回true。 - 如果遍历完所有可能的起点后，
dfs均未成功，则说明单词不存在于网格中，程序最后返回false。
-
核心搜索逻辑（DFS 与回溯）：
dfs(i, j, k, ...)是一个递归函数，负责从单元格(i, j)开始，尝试匹配word中从第k个字符开始的剩余部分。- 剪枝与基准情况：
- 失败剪枝：如果当前单元格
(i, j)超出边界（在递归调用前检查），或者其字符board[i][j]与目标字符word[k]不匹配，则此路不通，直接返回false。 - 成功基准：如果当前字符匹配，并且这已经是单词的最后一个字符（
k == word.length - 1），则说明整个单词已经成功匹配，返回true。
- 失败剪枝：如果当前单元格
- 递归与回溯：
- 标记（Marking）：为了防止在同一路径中重复使用单元格，在深入探索之前，代码会将当前单元格
board[i][j]的值临时修改为一个特殊标记（如此代码中的0）。这相当于一个“正在访问”的标记。 - 探索（Exploration）：接着，代码会向当前单元格的四个相邻方向（上、下、左、右）进行递归调用
dfs(x, y, k + 1, ...)，尝试匹配单词的下一个字符。 - 回溯（Backtracking）：在四个方向的递归探索完成之后（无论成功还是失败），必须将当前单元格
board[i][j]的值恢复为其原始字符word[k]。这是回溯算法的精髓，它确保了在探索其他起始点的路径时，该单元格是可用的。 - 如果四个方向的探索都没有找到完整的路径，则从当前点出发的搜索失败，返回
false。
- 标记（Marking）：为了防止在同一路径中重复使用单元格，在深入探索之前，代码会将当前单元格
完整代码
class Solution {// 定义一个常量数组，用于表示四个方向的坐标偏移量：右、左、下、上private static final int[][] DIRECTION = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};/*** 在二维字符网格中查找是否存在一个给定的单词。* @param board 二维字符网格* @param word 要查找的单词* @return 如果单词存在，返回 true；否则，返回 false。*/public boolean exist(char[][] board, String word) {// 将目标单词转换为字符数组，以提高后续字符访问的效率char[] w = word.toCharArray();// 遍历网格中的每一个单元格，将其作为单词搜索的潜在起点for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {// 从 (i, j) 开始进行深度优先搜索，尝试匹配单词的第一个字符 (k=0)if (dfs(i, j, 0, board, w)) {// 如果找到了一个完整的路径，立即返回 truereturn true;}}}// 如果遍历完所有可能的起点都未能找到单词，则返回 falsereturn false;}/*** 深度优先搜索辅助函数。* @param i 当前搜索的行索引* @param j 当前搜索的列索引* @param k 当前要匹配的目标单词中的字符索引* @param board 字符网格* @param word 目标单词的字符数组* @return 如果从 (i, j) 出发能找到 word[k...] 的路径，返回 true*/private boolean dfs(int i, int j, int k, char[][] board, char[] word) {// 剪枝：如果当前单元格的字符与目标字符不匹配，此路不通if (board[i][j] != word[k]) {return false;}// 成功基准：如果当前字符匹配，并且已是单词的最后一个字符，则搜索成功if (k == word.length - 1) {return true;}// 关键【标记】步骤：将当前单元格标记为已访问，防止在同一路径中重复使用。// 这里用一个非字符值（如0）来标记，也可以用一个不会在 board 和 word 中出现的特殊字符。board[i][j] = 0; // 探索四个相邻的方向for (int[] dir : DIRECTION) {int x = dir[0] + i;int y = dir[1] + j;// 检查新坐标 (x, y) 是否在网格边界内if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {// 对有效的相邻单元格进行递归调用，尝试匹配单词的下一个字符 (k+1)if (dfs(x, y, k + 1, board, word)) {// 如果任意方向的递归探索成功，立即返回 truereturn true;}}}// 关键【回溯】步骤：恢复当前单元格的原始值。// 这样，在回溯到上一个状态后，其他分支的搜索路径仍然可以使用此单元格。board[i][j] = word[k];// 如果所有方向都探索完毕，仍未找到匹配路径，则返回 falsereturn false;}
}
时空复杂度
时间复杂度：O(M * N * 3^L)
- 外层循环：
exist方法中的两层for循环遍历了整个网格，这部分是M * N次操作，其中M是行数，N是列数。 - DFS 复杂度：对于每个起点，都会调用
dfs函数。在dfs函数中，每次递归都会向最多 3 个新的方向探索（因为不能走回头路，而修改board值的操作天然地防止了这一点）。 - 递归深度：递归的最大深度由单词的长度
L决定。 - 综合分析：
- 在最坏的情况下，对于网格中的每个单元格
(M * N)，我们都可能启动一次深度优先搜索。 - 每次搜索的计算量大致可以估算为
3^L，因为每一步都有最多3个选择，持续L步。 - 因此，总的时间复杂度是一个粗略的上限：O(M * N * 3^L)，其中
L是单词word的长度。
- 在最坏的情况下，对于网格中的每个单元格
空间复杂度：O(L)
- 主要存储开销：算法的额外空间开销主要来自于递归调用栈。
- 递归深度：
dfs函数的递归深度取决于正在匹配的单词的长度。在最坏的情况下，当成功匹配到单词的最后一个字母时，递归栈的深度会达到L。 - 其他变量：
w = word.toCharArray(): 占用了 O(L) 的空间。DIRECTION数组：占用 O(1) 的常数空间。- 递归函数中的局部变量：占用 O(1) 空间。
综合分析：
递归栈的深度是空间复杂度的主要部分。因此，算法的空间复杂度为 O(L)，其中 L 是单词 word 的长度。
参考灵神