【日常工作计划及排期平台】开发实践
2026/7/18 5:59:25
本题采用回溯剪枝算法（又称“深度优先搜索现场染色与回溯重置法”）解决二维字符网格路径搜索与匹配问题。其核心本质是将一维字符串在二维网格中的非线性搜索转化为多叉决策树的分支探测，利用原地占位标记实现路径无重复性物理校验，并在回溯时撤销状态。当前提供的源码通过在递归入口统一进行边界校验与不匹配剪枝，实现了在大规模状态空间下的最优剪枝与时空控制，最终走向是精准判定目标单词是否能物理嵌入网格。
一、 问题本质与数据模型
对于大小为 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)。