Problem: 79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

整体思路

这段代码旨在解决一个经典的二维网格搜索问题：单词搜索 (Word Search)。其核心功能是判断一个给定的单词 word 是否存在于一个字符网格 board 中。构成单词的路径规则是：字母必须在网格中水平或垂直相邻，并且同一个单元格的字母在路径中不允许被重复使用。

该算法采用了 深度优先搜索（DFS） 结合 回溯（Backtracking） 的策略。其整体思路可以分解为以下几个步骤：

1. 主驱动逻辑（遍历所有起点）：

   • exist 方法是算法的入口。它通过两层嵌套的 for 循环遍历网格 board 中的每一个单元格 (i, j)。
   • 这个遍历的目的是将每一个单元格都视作单词 word 的一个潜在 起始点。
   • 对于每一个起点，它都会调用核心的 dfs 辅助函数来尝试进行深度搜索。如果任何一次 dfs 调用返回 true，意味着找到了完整的单词路径，程序立即返回 true。
   • 如果遍历完所有可能的起点后，dfs 均未成功，则说明单词不存在于网格中，程序最后返回 false。

2. 核心搜索逻辑（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。

完整代码

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)

1. 外层循环：exist 方法中的两层 for 循环遍历了整个网格，这部分是 M * N 次操作，其中 M 是行数，N 是列数。
2. DFS 复杂度：对于每个起点，都会调用 dfs 函数。在 dfs 函数中，每次递归都会向最多 3 个新的方向探索（因为不能走回头路，而修改 board 值的操作天然地防止了这一点）。
3. 递归深度：递归的最大深度由单词的长度 L 决定。
4. 综合分析：
   • 在最坏的情况下，对于网格中的每个单元格 (M * N)，我们都可能启动一次深度优先搜索。
   • 每次搜索的计算量大致可以估算为 3^L，因为每一步都有最多3个选择，持续 L 步。
   • 因此，总的时间复杂度是一个粗略的上限：O(M * N * 3^L)，其中 L 是单词 word 的长度。

空间复杂度：O(L)

1. 主要存储开销：算法的额外空间开销主要来自于递归调用栈。
2. 递归深度：dfs 函数的递归深度取决于正在匹配的单词的长度。在最坏的情况下，当成功匹配到单词的最后一个字母时，递归栈的深度会达到 L。
3. 其他变量：
   • w = word.toCharArray(): 占用了 O(L) 的空间。
   • DIRECTION 数组：占用 O(1) 的常数空间。
   • 递归函数中的局部变量：占用 O(1) 空间。

综合分析：
递归栈的深度是空间复杂度的主要部分。因此，算法的空间复杂度为 O(L)，其中 L 是单词 word 的长度。

参考灵神