hot100 单词搜索(79)

本题采用回溯剪枝算法又称“深度优先搜索现场染色与回溯重置法”解决二维字符网格路径搜索与匹配问题。其核心本质是将一维字符串在二维网格中的非线性搜索转化为多叉决策树的分支探测利用原地占位标记实现路径无重复性物理校验并在回溯时撤销状态。当前提供的源码通过在递归入口统一进行边界校验与不匹配剪枝实现了在大规模状态空间下的最优剪枝与时空控制最终走向是精准判定目标单词是否能物理嵌入网格。一、 问题本质与数据模型对于大小为 m x n 的二维字符网格 board 和目标单词 word题目要求在网格中寻找一条能完整匹配该单词的物理路径。该问题面临两个核心物理约束相邻连通约束路径中的相邻字符必须在水平左右或竖直上下方向上相邻。节点排他约束在同一条路径中同一个单元格内的字符只能使用一次。为了在搜索过程中严格遵守这些约束算法引入了“原地染色回溯模型”。常规的图遍历中若不加标记地任意探索极易导致路径在局部节点间来回振荡例如在 “AB” 和 “BA” 之间死循环。本算法通过在匹配当前字符word[k]时将board[i][j]暂时篡改为一个非字母的特殊标记占位符0从而在当前的向下深探链条中屏蔽该节点。由于任意合法的英文字母都不等于0这在物理上构成了一个隐式的屏障阻断了路径的自环。在当前分支探测完毕回溯时算法再将board[i][j]还原为原字符word[k]恢复网格初始状态。这种轻量级的现场保护机制避免了额外的状态重算。二、 算法演进对比在解决二维网格单词搜索问题时原地回溯法在时空资源的利用率上表现优异解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷常规 visited 辅助矩阵法O(m * n * 3^L)O(m * n)申请一个同等规模的布尔矩阵记录节点的访问状态每次检索前进行状态变更每次运行均需在堆内存中开辟和释放二维布尔数组增加了垃圾回收GC的负担原地标记与延迟校验当前解法O(m * n * 3^L)O(L)利用当前元素原地覆写 0 标记不提前在外部校验边界全部交由递归入口统一处理依赖系统的方法调用栈在单词长度 L 极大时栈开销与 L 呈线性正比例关系字典树Trie与回溯联合定位O(m * n * 3^L)O(V)针对多单词搜索将所有目标词构建为 Trie 树回溯时在树上多路并进空间开销极大V 为字典树节点数若只搜索单一单词构建字典树将产生严重的算力浪费三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于外层双重循环起点检索与内层 DFS 的延迟校验逻辑其内部决策分支证明如下1. 成功出口判定if (k word.length)执行直接返回 true。物理意义当匹配指针k递增到等于目标单词的长度word.length时代表在前一个递归层级k - 1中单词的最后一个字符已经成功通过了边界检查和匹配检查。因此完整的单词匹配已经完成递归应立即终止并向上层回溯。2. 统一边界与剪枝核验if (i 0 || i board.length || ... || board[i][j] ! word[k])执行直接返回 false。数学证明这是一个多合一的防护网i或j越界证明当前搜索路径已经脱离了矩阵实体。board[i][j] ! word[k]说明当前网格字符不匹配目标单词中的第 k 个字符或者当前单元格已被置为0因为0绝对不等于任何字母。结论只要上述任意条件成立当前分支直接判定为死胡同触发即时剪枝并返回 false。3. 延迟校验设计for (int[] d : dir) { ... dfs(board, word, x, y, k 1) }执行直接将计算后的下一级坐标传入dfs不提前在外部进行x 0等合法性判断。数学证明这种做法消除了冗余的外部判断将所有的安全防护逻辑统一收拢到递归函数的最顶部。既保证了代码结构的高内聚又避免了在每一次分支跳转时重复进行复杂的坐标边界计算提升了分支预测的效率。4. 原地修改与回溯复原board[i][j] 0; ... board[i][j] word[k];执行在深入下一层递归前将字符临时改写为 0在回溯时重新写回原字符。数学证明将状态污染局限在以当前节点为根的子决策树内部。由于回溯时执行了无条件复原保证了不同起点的搜索路径以及并行的同级分支不会受到其他分支历史探索状态的干扰。四、 算法执行状态机步进示例以输入网格board [ [A, B], [C, D] ]目标单词word ABD为例规模 2 x 2单词长度 L 3展示算法在锁定唯一合法路径时的状态机变迁过程其中已访问的单元格物理数值变为 0步骤当前递归坐标 (i, j)当前匹配指针 k网格当前物理状态 (2x2 状态快照)分支判定条件与执行动作空间调用栈状态初始(0, 0)0[ [A, B], [C, D] ]字符匹配 A A进入现场染色栈深: [ (0,0) ]1(0, 0)0[ [ 0, B], [C, D] ]探索右方 (0, 1)调用dfs(board, word, 0, 1, 1)栈深: [ (0,0) ]2(0, 1)1[ [ 0, B], [C, D] ]字符匹配 B B进入现场染色栈深: [ (0,0), (0,1) ]3(0, 1)1[ [ 0, 0 ], [C, D] ]探索下方 (1, 1)调用dfs(board, word, 1, 1, 2)栈深: [ (0,0), (0,1) ]4(1, 1)2[ [ 0, 0 ], [C, D] ]字符匹配 D D进入现场染色栈深: [ (0,0), (0,1), (1,1) ]5(1, 1)2[ [ 0, 0 ], [C, 0 ] ]探测任意一向例如 (1,2)调用dfs(..., 3)栈深: [ (0,0), (0,1), (1,1) ]6(1, 2)3-满足出口条件k 3无视越界直接返回 true触发全链路回溯终值--[ [A, B], [C, D] ]状态逐层恢复返回最终结果 true调用栈清空检索成功五、 源码实现class Solution { public boolean exist(char[][] board, String word) { // 双重线性扫描穷举矩阵中的每一个坐标作为匹配单词的起点 for (int i 0; i board.length; i) { for (int j 0; j board[0].length; j) { // 条件控制若当前起点能够成功延展匹配出完整单词立刻判定存在 if (dfs(board, word.toCharArray(), i, j, 0)) { return true; } } } // 若遍历完全部格点仍无一条路径能够走通则返回判定失败 return false; } // 静态方向矩阵映射依次代表向右、向下、向左、向上四个物理移动偏移行程 private int[][] dir new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; private boolean dfs(char[][] board, char[] word, int i, int j, int k) { // 条件分支 1成功出口只要 k 达到了 word 长度说明前一层的字符已经全部匹配完毕 if (k word.length) { return true; } // 条件分支 2边界核验与剪枝统一检测下标越界、字符不匹配以及重复访问0 ! word[k] if (i 0 || i board.length || j 0 || j board[0].length || board[i][j] ! word[k]) { return false; } // 原地状态染色将当前节点物理改写为 0防止当前路径向下深探时自环 board[i][j] 0; // 核心控制采用延迟校验机制直接计算偏移量并压入下一层递归 for (int[] d : dir) { int x i d[0]; int y j d[1]; // 只要有任意一个方向的分支能走通就一键向上传递 true if (dfs(board, word, x, y, k 1)) { return true; } } // 状态回溯复原由于当前层级未能在后续分支中匹配成功还原字符以供其他路径重用 board[i][j] word[k]; // 返回失败信号告知父级调用栈当前分支不可行 return false; } }六、 复杂度分析1. 时间复杂度O(m * n * 3^L)分析算法的外层执行了完整的双重嵌套循环共提供了 m * n 个可能的探测起点。对于每一个起点发起的 DFS 回溯其递归的最大深度等于目标单词的长度 L。在搜索的第一个节点上我们有 4 个可行的扩散方向但在随后的深探步骤中由于前驱节点已被设为 0 拦截所以每一个后继节点至多只有 3 个可选的未访问方向除去来时的方向。因此单次 DFS 探测的分支总数上限为 4 * 3^(L - 1)。结论在最坏情况下即网格全为相同字母且几乎所有路径都在最后一步匹配失败总的时间复杂度为 O(m * n * 3^L)。由于提示中限制了 L 15所以该回溯规模属于常数级可控范围。2. 空间复杂度O(L)分析算法直接利用了输入网格board进行原地覆写染色消除了辅助visited矩阵的使用这一部分的堆内存开销被完美压缩至 O(1)。在运行期间空间的动态开销完全由隐式的方法调用栈深度决定。因为递归只有在匹配成功或剪枝失败时才会返回所以系统调用栈的最大物理深度等于目标单词的长度 L。结论最大额外栈空间消耗表示为 O(L)。