1. 题目描述1.1 原始题目给定一个m x n二维字符网格board和一个字符串单词word判断word是否存在于网格中。规则约束路径构成路径必须沿着上下左右四个方向相邻单元格依次连接字母顺序路径上的字母必须与 word 字母顺序完全一致唯一使用同一个单元格内的字母不允许被重复使用大小写敏感board 和 word 仅由大小写英文字母组成1.2 示例详解示例 1board [ [A,B,C,E], [S,F,C,S], [A,D,E,E] ] word ABCCED 输出true路径A(0,0) - B(0,1) - C(0,2) - C(1,2) - E(2,2) - D(2,1)A B C E 起点A S F C S -- 右-B - 下-C(同列) - 右-C(同行) - 下-E - 左-D A D E E 路径构成 ABCCED示例 2board [ [A,B,C,E], [S,F,C,S], [A,D,E,E] ] word SEE 输出true路径S(1,0) - E(1,3) - E(2,3)或E(2,2) - E(2,3)A B C E 起点S S F C S -- 右-F - C - S - E - E A D E E 或直接从E开始示例 3board [ [A,B,C,E], [S,F,C,S], [A,D,E,E] ] word ABCB 输出false失败原因第三个字符是’C’但网格中相邻的’C’被第一个’C’占据无法绕开A B C E 尝试路径 A - B - C(0,2) - ? S F C S -- 第四个字符是B但(0,3)是E(1,2)是C(1,1)是F A D E E 上下左右都没有B搜索失败1.3 约束分析1 m, n 6 -- board 很小最多36个单元格 1 word.length 15 -- word 长度较短重要虽然约束看起来小但暴力搜索仍是指数级别需要剪枝优化。2. 解题思路总览2.1 核心思想步骤操作目的1从board每个单元格作为起点覆盖所有可能的起点2检查起点字符是否匹配word[0]不匹配直接跳过3上下左右四个方向递归搜索尝试所有路径4标记已访问单元格防止重复使用5搜索失败则回溯恢复让其他路径可以使用该单元格2.2 方法对比方法时间复杂度空间复杂度适用场景暴力DFSO(MN4^L)O(L)小规模数据剪枝优化DFS最坏仍指数级O(L)一般场景本题Trie优化O(MNL)O(Trie大小)多单词搜索(212题)本文重点剪枝优化的DFS solution2.3 思路演进第一版暴力DFS会超时// 错误写法没有访问标记会重复使用单元格booldfs(inti,intj,intk){if(board[i][j]!word[k])returnfalse;if(kword.length()-1)returntrue;foreach direction:if(dfs(ii,jj,k1))returntrue;returnfalse;}问题没有标记已访问同一个单元格会被重复使用导致错误结果。第二版bool数组标记boolvisited[6][6];booldfs(inti,intj,intk){if(board[i][j]!word[k])returnfalse;if(kword.length()-1)returntrue;visited[i][j]true;foreach direction:if(!visited[ii][jj]dfs(ii,jj,k1))returntrue;visited[i][j]false;// 回溯恢复returnfalse;}优点正确处理重复使用问题缺点需要额外的visited数组空间开销第三版原地标记本题解法// 直接修改board用0标记已访问board[i][j]0;// 标记// ... 搜索board[i][j]word[k];// 回溯恢复优点O(1)空间无需额外数组原因board中只有字母0不可能是任何字母可作为特殊标记3. 完整代码classSolution{public:boolexist(vectorvectorcharboard,string word){intmboard.size(),nboard[0].size();// 四个方向的偏移量右、下、左、上intdic[4][2]{{0,1},{1,0},{0,-1},{-1,0}};// 使用lambda定义递归DFS函数autodfs[](thisautodfs,inti,intj,intk)-bool{// 第一步检查当前字符是否匹配// 不匹配直接返回false这是最基础的剪枝if(board[i][j]!word[k])returnfalse;// 第二步递归终止条件// 已经匹配到word的最后一个字符说明路径完整if(k1word.length())returntrue;// 第三步标记为已访问// 用字符0作为标记因为0不是任何字母board[i][j]0;// 第四步尝试四个方向的递归搜索for(auto[x,y]:dic){intiiix,jjjy;// 先检查边界防止越界if(0iiiim0jjjjn){// 如果找到一条可行路径立即返回trueif(dfs(ii,jj,k1))returntrue;}}// 第五步回溯恢复现场// 无论搜索成功与否都要恢复原始字符board[i][j]word[k];// 第六步四个方向都走不通返回falsereturnfalse;};// 枚举board中的每一个单元格作为起点for(inti0;im;i){for(intj0;jn;j){if(dfs(i,j,0))returntrue;}}returnfalse;}};4. 算法流程图4.1 主函数流程[开始] | v --- for i in [0, m) | | | v | for j in [0, n) | | | v | dfs(i, j, 0) | | | v ---- return true? --- [结束: true] 否 是4.2 DFS函数详细流程dfs(i, j, k) | v ----- board[i][j] word[k]? | 否 | 是 | v v | return false k1 word.length()? | | 是 | v | return true | | 否 | v | board[i][j] 0 (标记) | | | v | for dir in dic[4] | | | v | ii i dir.x | jj j dir.y | | | v | (ii, jj)在边界内? | 否| |是 | v v | 跳过 dfs(ii, jj, k1) | | | v | dfs返回true? --- return true | 否 | v | 继续下一方向 | | ---- 所有方向遍历完 | v board[i][j] word[k] (回溯恢复) | v return false4.3 回溯过程图解以搜索 “ABCB” 为例展示回溯过程初始board: 第一步起点A(0,0) A B C E board[0][0] 0 标记 S F C S ↓ A D E E 0 B C E S F C S A D E E 搜索到C(0,2)后 第二步继续搜索B失败 0 B 0 E ↓ S F 0 S 0 B 0 E A D E E S F 0 S A D E E 回溯恢复C(0,2) 第三步尝试其他方向 0 B C E ↓ S F C S 0 B C E A D E E S F C S ↓ [回溯树往上走换方向]5. 逐行深度解析5.1 方向数组的定义intdic[4][2]{{0,1},{1,0},{0,-1},{-1,0}};方向索引dxdy含义右001列1行不变下110行1列不变左20-1列-1行不变上3-10行-1列不变为什么这样安排右手坐标系假设以左上角为原点向右为x正方向向下为y正方向先横后纵的搜索顺序符合人类阅读习惯也可以用其他顺序不影响结果5.2 递归lambda的定义autodfs[](thisautodfs,inti,intj,intk)-bool{语法含义auto dfs使用auto类型推导捕获方式为引用可以访问外部变量m, n, dic, board, wordthis auto dfsC23显式递归声明允许lambda内部调用自身int i, int j当前单元格坐标int k当前匹配到word的第k个字符0-indexed为什么用lambda而不是普通函数可以直接访问外部变量board, word, dic, m, n代码更紧凑逻辑更清晰现代C推荐写法注意this auto dfs是C23语法如果编译器不支持可改为functionbool(int,int,int)dfs[](inti,intj,intk)-bool{// ...returndfs(ii,jj,k1);// 递归调用};5.3 字符匹配检查if(board[i][j]!word[k])returnfalse;时机每次进入递归的第一步作用剪枝的最基本形式不匹配就立即返回等价写法if(board[i][j]word[k]){// 匹配继续搜索}else{returnfalse;}5.4 递归终止条件if(k1word.length())returntrue;含义已经匹配到word的最后一个字符k值word[k]说明0第一个字符刚检查完第一个字符1第二个字符已匹配2个字符………word.length()-1最后一个字符已匹配所有字符等价的终止条件写法if(kword.length()-1)returntrue;// 更直观if(kword.size())returntrue;// 如果k是下一个要匹配的位置5.5 访问标记的奥秘board[i][j]0;为什么用0而不是其他字符board和word仅包含大小写字母0’的ASCII值是48A’是65a’是970’不可能与任何合法字符冲突用完后恢复原值可以无损还原为什么不用visited数组省去额外空间直接利用board本身代码更简洁但修改了输入数组如果介意可先拷贝5.6 四方向搜索循环for(auto[x,y]:dic){intiiix,jjjy;if(0iiiim0jjjjn){if(dfs(ii,jj,k1))returntrue;}}结构分析for (遍历四个方向) { 计算新坐标 (ii, jj) | v 边界检查 (ii, jj) 是否在 [0,m) x [0,n) 内 | 否 -- continue 跳过该方向 | 是 v 递归搜索 dfs(ii, jj, k1) | v 找到解 -- return true }注意找到解就立即return不继续搜索5.7 回溯恢复现场board[i][j]word[k];returnfalse;为什么要回溯搜索路径A-B-C时标记了A、B、C三个位置如果从C出发四条路都走不通需要返回到B返回到B后B需要尝试其他方向比如向下此时C不能再被使用需要恢复所以必须恢复现场让其他分支可以正常使用该单元格回溯的时机只有在当前递归的所有方向都失败时才执行一旦找到解return true不会执行到回溯5.8 起点枚举for(inti0;im;i){for(intj0;jn;j){if(dfs(i,j,0))returntrue;}}returnfalse;枚举的意义word的第一个字符可能在board的任何位置只有起点字符匹配word[0]时才会进入DFS只要有一个起点能搜到完整路径就返回true优化写法先检查首字符for(inti0;im;i){for(intj0;jn;j){if(board[i][j]word[0]dfs(i,j,0))returntrue;}}6. 复杂度分析6.1 时间复杂度详细推导T(M, N, L) M * N * 4^L推导过程外层枚举起点M * N 个每个起点最坏情况向四个方向各走L步每一步有4个选择上下左右总搜索空间4 * 4 * … * 4 (L次) 4^L实际情况不会达到4^L因为边界限制边缘方向走不通匹配限制字母不匹配立即返回访问限制已访问单元格不能重复使用剪枝效果无剪枝 4^L 有剪枝后 实际搜索次数 4^L 典型情况几十到几百次6.2 空间复杂度S(L) O(L)组成递归调用栈的深度最多L层word长度每层递归只需要保存 i, j, k 三个int参数注意如果算上board本身的O(MN)空间则总空间为O(MN)7. 搜索过程详解7.1 示例“ABCCED” 的完整搜索过程boardA B C E S F C S A D E Eword “ABCCED”长度6起点枚举阶段 - 检查A(0,0)board[0][0] A word[0]进入DFS - 检查其他起点都不匹配word[0]A 从A(0,0)开始的DFS depth0: A(0,0), k0, board[0][0]A word[0]A ✓ 标记 board[0][0]0 四个方向尝试 - 右B(0,1)进入depth1 depth1: B(0,1), k1, board[0][1]B word[1]B ✓ 标记 board[0][1]0 四个方向尝试 - 右C(0,2)进入depth2 depth2: C(0,2), k2, board[0][2]C word[2]C ✓ 标记 board[0][2]0 四个方向尝试 - 右E(0,3)进入depth3 depth3: E(0,3), k3, board[0][3]E word[3]E ✓ ...继续搜索E(2,2) - 下C(1,2)进入depth3 depth3: C(1,2), k3, board[1][2]C word[3]E ✗ 返回false - 左B(0,1)已标记(值为0)跳过 - 上越界跳过 恢复 board[0][2]C 返回false其他方向也都失败 - 下C(1,1)board[1][1]F ! C ✗ - 左越界 - 上越界 恢复 board[0][1]B 返回false - 下S(1,0)board[1][0]S ! B ✗ - 其他方向类似... 恢复 board[0][0]A 返回false 继续枚举下一个起点 - A(2,0)board[2][0]A word[0]A ✓ 找到完整路径ABCCED 返回true7.2 回溯失败的典型场景搜索 “ABCB”depth0: A(0,0), k0, A A ✓标记为0 depth1: B(0,1), k1, B B ✓标记为0 depth2: C(0,2), k2, C C ✓标记为0 depth3: 尝试找B - 右E(0,3): E ! B ✗ - 下C(1,2): 标记0已访问✗ - 左B(0,1): 标记0已访问✗ - 上越界 depth3全部失败恢复board[0][2]C 返回false depth2返回false恢复board[0][1]B depth1返回false恢复board[0][0]A 尝试其他起点...全部失败 返回false8. 易错点分析8.1 边界检查顺序错误写法intiiix,jjjy;if(dfs(ii,jj,k1))// 先递归再检查边界可能越界正确写法intiiix,jjjy;if(0iiiim0jjjjn){if(dfs(ii,jj,k1))// 先检查再递归}原因DFS内部会访问board[ii][jj]越界会导致未定义行为8.2 标记值的选取错误写法board[i][j]X;// 如果word包含X会出问题board[i][j]board[i][j];// 没有实际标记正确写法board[i][j]0;// 0不是字母可作为特殊标记8.3 回溯时机错误写法board[i][j]0;// 标记if(dfs(ii,jj,k1))returntrue;// 忘记回溯恢复returnfalse;后果其他分支无法使用该单元格导致漏解8.4 递归终止条件位置错误写法if(k1word.length())returntrue;if(board[i][j]!word[k])returnfalse;// 终止条件应该在匹配检查之后后果最后一个字符匹配后还会继续搜索8.5 外层循环遗漏错误写法// 没有从每个单元格作为起点枚举if(dfs(0,0,0))returntrue;// 只从(0,0)开始搜索后果如果word的第一个字符不在(0,0)位置会漏解9. 边界条件测试9.1 单单元格boardboard [[A]] word A -- true (正好一个字符) word AA -- false (字符不够)9.2 单行/单列boardboard [[A,B,C]] word ABC -- true (只能向右) word ACB -- false (不能向后走)9.3 word长度1board 任意 word A -- 只要board中有A就返回true9.4 word长度board面积board [[A,B],[C,D]] (4个单元格) word ABCDEF -- false (单元格不够用)9.5 全相同字符board [[A,A],[A,A]] word AAA -- true (可以从任意起点开始) word AAAA -- false (只有4个单元格)10. 面试追问 FAQ问题高分回答为什么用0标记而不是visited数组因为board中只有字母0不可能是任何字母可以作为天然的特殊标记节省O(M*N)空间如何进一步优化1) 先统计word和board的字符频率不匹配直接返回2) 使用Trie树优化多单词搜索3) 预计算每个字符的位置列表能处理word中有重复字符吗能因为每个单元格只能使用一次不是word中的字符不能重复使用如果board很大怎么办先检查board中是否包含word的所有字符或使用BFS剪枝或使用Trie预筛选回溯的本质是什么回溯是恢复现场让其他搜索路径可以使用被当前路径独占的单元格递归栈溢出怎么办word长度最多15不会溢出如果更长可改为显示栈模拟DFS和212题单词搜索II有什么区别212题是找所有存在于board中的单词需要TrieDFS本题只需判断一个单词是否存在11. 相关题目对比题号题目难度核心区别79单词搜索Medium判断单个单词是否存在212单词搜索 IIHard找出所有存在的单词需要Trie130被围绕的区域MediumDFS变体标记被围绕的’O’200岛屿数量MediumDFS遍历计数连通区域463岛屿的周长EasyDFS/BFS计算周长12. 总结要点详情算法深度优先搜索 回溯标记方法原地修改board用0标记已访问回溯时机递归返回前恢复现场剪枝策略字符不匹配立即返回找到解立即返回时间复杂度O(MN4^L)最坏指数级空间复杂度O(L)递归栈深度
【力扣100题】73.单词搜索
1. 题目描述1.1 原始题目给定一个m x n二维字符网格board和一个字符串单词word判断word是否存在于网格中。规则约束路径构成路径必须沿着上下左右四个方向相邻单元格依次连接字母顺序路径上的字母必须与 word 字母顺序完全一致唯一使用同一个单元格内的字母不允许被重复使用大小写敏感board 和 word 仅由大小写英文字母组成1.2 示例详解示例 1board [ [A,B,C,E], [S,F,C,S], [A,D,E,E] ] word ABCCED 输出true路径A(0,0) - B(0,1) - C(0,2) - C(1,2) - E(2,2) - D(2,1)A B C E 起点A S F C S -- 右-B - 下-C(同列) - 右-C(同行) - 下-E - 左-D A D E E 路径构成 ABCCED示例 2board [ [A,B,C,E], [S,F,C,S], [A,D,E,E] ] word SEE 输出true路径S(1,0) - E(1,3) - E(2,3)或E(2,2) - E(2,3)A B C E 起点S S F C S -- 右-F - C - S - E - E A D E E 或直接从E开始示例 3board [ [A,B,C,E], [S,F,C,S], [A,D,E,E] ] word ABCB 输出false失败原因第三个字符是’C’但网格中相邻的’C’被第一个’C’占据无法绕开A B C E 尝试路径 A - B - C(0,2) - ? S F C S -- 第四个字符是B但(0,3)是E(1,2)是C(1,1)是F A D E E 上下左右都没有B搜索失败1.3 约束分析1 m, n 6 -- board 很小最多36个单元格 1 word.length 15 -- word 长度较短重要虽然约束看起来小但暴力搜索仍是指数级别需要剪枝优化。2. 解题思路总览2.1 核心思想步骤操作目的1从board每个单元格作为起点覆盖所有可能的起点2检查起点字符是否匹配word[0]不匹配直接跳过3上下左右四个方向递归搜索尝试所有路径4标记已访问单元格防止重复使用5搜索失败则回溯恢复让其他路径可以使用该单元格2.2 方法对比方法时间复杂度空间复杂度适用场景暴力DFSO(MN4^L)O(L)小规模数据剪枝优化DFS最坏仍指数级O(L)一般场景本题Trie优化O(MNL)O(Trie大小)多单词搜索(212题)本文重点剪枝优化的DFS solution2.3 思路演进第一版暴力DFS会超时// 错误写法没有访问标记会重复使用单元格booldfs(inti,intj,intk){if(board[i][j]!word[k])returnfalse;if(kword.length()-1)returntrue;foreach direction:if(dfs(ii,jj,k1))returntrue;returnfalse;}问题没有标记已访问同一个单元格会被重复使用导致错误结果。第二版bool数组标记boolvisited[6][6];booldfs(inti,intj,intk){if(board[i][j]!word[k])returnfalse;if(kword.length()-1)returntrue;visited[i][j]true;foreach direction:if(!visited[ii][jj]dfs(ii,jj,k1))returntrue;visited[i][j]false;// 回溯恢复returnfalse;}优点正确处理重复使用问题缺点需要额外的visited数组空间开销第三版原地标记本题解法// 直接修改board用0标记已访问board[i][j]0;// 标记// ... 搜索board[i][j]word[k];// 回溯恢复优点O(1)空间无需额外数组原因board中只有字母0不可能是任何字母可作为特殊标记3. 完整代码classSolution{public:boolexist(vectorvectorcharboard,string word){intmboard.size(),nboard[0].size();// 四个方向的偏移量右、下、左、上intdic[4][2]{{0,1},{1,0},{0,-1},{-1,0}};// 使用lambda定义递归DFS函数autodfs[](thisautodfs,inti,intj,intk)-bool{// 第一步检查当前字符是否匹配// 不匹配直接返回false这是最基础的剪枝if(board[i][j]!word[k])returnfalse;// 第二步递归终止条件// 已经匹配到word的最后一个字符说明路径完整if(k1word.length())returntrue;// 第三步标记为已访问// 用字符0作为标记因为0不是任何字母board[i][j]0;// 第四步尝试四个方向的递归搜索for(auto[x,y]:dic){intiiix,jjjy;// 先检查边界防止越界if(0iiiim0jjjjn){// 如果找到一条可行路径立即返回trueif(dfs(ii,jj,k1))returntrue;}}// 第五步回溯恢复现场// 无论搜索成功与否都要恢复原始字符board[i][j]word[k];// 第六步四个方向都走不通返回falsereturnfalse;};// 枚举board中的每一个单元格作为起点for(inti0;im;i){for(intj0;jn;j){if(dfs(i,j,0))returntrue;}}returnfalse;}};4. 算法流程图4.1 主函数流程[开始] | v --- for i in [0, m) | | | v | for j in [0, n) | | | v | dfs(i, j, 0) | | | v ---- return true? --- [结束: true] 否 是4.2 DFS函数详细流程dfs(i, j, k) | v ----- board[i][j] word[k]? | 否 | 是 | v v | return false k1 word.length()? | | 是 | v | return true | | 否 | v | board[i][j] 0 (标记) | | | v | for dir in dic[4] | | | v | ii i dir.x | jj j dir.y | | | v | (ii, jj)在边界内? | 否| |是 | v v | 跳过 dfs(ii, jj, k1) | | | v | dfs返回true? --- return true | 否 | v | 继续下一方向 | | ---- 所有方向遍历完 | v board[i][j] word[k] (回溯恢复) | v return false4.3 回溯过程图解以搜索 “ABCB” 为例展示回溯过程初始board: 第一步起点A(0,0) A B C E board[0][0] 0 标记 S F C S ↓ A D E E 0 B C E S F C S A D E E 搜索到C(0,2)后 第二步继续搜索B失败 0 B 0 E ↓ S F 0 S 0 B 0 E A D E E S F 0 S A D E E 回溯恢复C(0,2) 第三步尝试其他方向 0 B C E ↓ S F C S 0 B C E A D E E S F C S ↓ [回溯树往上走换方向]5. 逐行深度解析5.1 方向数组的定义intdic[4][2]{{0,1},{1,0},{0,-1},{-1,0}};方向索引dxdy含义右001列1行不变下110行1列不变左20-1列-1行不变上3-10行-1列不变为什么这样安排右手坐标系假设以左上角为原点向右为x正方向向下为y正方向先横后纵的搜索顺序符合人类阅读习惯也可以用其他顺序不影响结果5.2 递归lambda的定义autodfs[](thisautodfs,inti,intj,intk)-bool{语法含义auto dfs使用auto类型推导捕获方式为引用可以访问外部变量m, n, dic, board, wordthis auto dfsC23显式递归声明允许lambda内部调用自身int i, int j当前单元格坐标int k当前匹配到word的第k个字符0-indexed为什么用lambda而不是普通函数可以直接访问外部变量board, word, dic, m, n代码更紧凑逻辑更清晰现代C推荐写法注意this auto dfs是C23语法如果编译器不支持可改为functionbool(int,int,int)dfs[](inti,intj,intk)-bool{// ...returndfs(ii,jj,k1);// 递归调用};5.3 字符匹配检查if(board[i][j]!word[k])returnfalse;时机每次进入递归的第一步作用剪枝的最基本形式不匹配就立即返回等价写法if(board[i][j]word[k]){// 匹配继续搜索}else{returnfalse;}5.4 递归终止条件if(k1word.length())returntrue;含义已经匹配到word的最后一个字符k值word[k]说明0第一个字符刚检查完第一个字符1第二个字符已匹配2个字符………word.length()-1最后一个字符已匹配所有字符等价的终止条件写法if(kword.length()-1)returntrue;// 更直观if(kword.size())returntrue;// 如果k是下一个要匹配的位置5.5 访问标记的奥秘board[i][j]0;为什么用0而不是其他字符board和word仅包含大小写字母0’的ASCII值是48A’是65a’是970’不可能与任何合法字符冲突用完后恢复原值可以无损还原为什么不用visited数组省去额外空间直接利用board本身代码更简洁但修改了输入数组如果介意可先拷贝5.6 四方向搜索循环for(auto[x,y]:dic){intiiix,jjjy;if(0iiiim0jjjjn){if(dfs(ii,jj,k1))returntrue;}}结构分析for (遍历四个方向) { 计算新坐标 (ii, jj) | v 边界检查 (ii, jj) 是否在 [0,m) x [0,n) 内 | 否 -- continue 跳过该方向 | 是 v 递归搜索 dfs(ii, jj, k1) | v 找到解 -- return true }注意找到解就立即return不继续搜索5.7 回溯恢复现场board[i][j]word[k];returnfalse;为什么要回溯搜索路径A-B-C时标记了A、B、C三个位置如果从C出发四条路都走不通需要返回到B返回到B后B需要尝试其他方向比如向下此时C不能再被使用需要恢复所以必须恢复现场让其他分支可以正常使用该单元格回溯的时机只有在当前递归的所有方向都失败时才执行一旦找到解return true不会执行到回溯5.8 起点枚举for(inti0;im;i){for(intj0;jn;j){if(dfs(i,j,0))returntrue;}}returnfalse;枚举的意义word的第一个字符可能在board的任何位置只有起点字符匹配word[0]时才会进入DFS只要有一个起点能搜到完整路径就返回true优化写法先检查首字符for(inti0;im;i){for(intj0;jn;j){if(board[i][j]word[0]dfs(i,j,0))returntrue;}}6. 复杂度分析6.1 时间复杂度详细推导T(M, N, L) M * N * 4^L推导过程外层枚举起点M * N 个每个起点最坏情况向四个方向各走L步每一步有4个选择上下左右总搜索空间4 * 4 * … * 4 (L次) 4^L实际情况不会达到4^L因为边界限制边缘方向走不通匹配限制字母不匹配立即返回访问限制已访问单元格不能重复使用剪枝效果无剪枝 4^L 有剪枝后 实际搜索次数 4^L 典型情况几十到几百次6.2 空间复杂度S(L) O(L)组成递归调用栈的深度最多L层word长度每层递归只需要保存 i, j, k 三个int参数注意如果算上board本身的O(MN)空间则总空间为O(MN)7. 搜索过程详解7.1 示例“ABCCED” 的完整搜索过程boardA B C E S F C S A D E Eword “ABCCED”长度6起点枚举阶段 - 检查A(0,0)board[0][0] A word[0]进入DFS - 检查其他起点都不匹配word[0]A 从A(0,0)开始的DFS depth0: A(0,0), k0, board[0][0]A word[0]A ✓ 标记 board[0][0]0 四个方向尝试 - 右B(0,1)进入depth1 depth1: B(0,1), k1, board[0][1]B word[1]B ✓ 标记 board[0][1]0 四个方向尝试 - 右C(0,2)进入depth2 depth2: C(0,2), k2, board[0][2]C word[2]C ✓ 标记 board[0][2]0 四个方向尝试 - 右E(0,3)进入depth3 depth3: E(0,3), k3, board[0][3]E word[3]E ✓ ...继续搜索E(2,2) - 下C(1,2)进入depth3 depth3: C(1,2), k3, board[1][2]C word[3]E ✗ 返回false - 左B(0,1)已标记(值为0)跳过 - 上越界跳过 恢复 board[0][2]C 返回false其他方向也都失败 - 下C(1,1)board[1][1]F ! C ✗ - 左越界 - 上越界 恢复 board[0][1]B 返回false - 下S(1,0)board[1][0]S ! B ✗ - 其他方向类似... 恢复 board[0][0]A 返回false 继续枚举下一个起点 - A(2,0)board[2][0]A word[0]A ✓ 找到完整路径ABCCED 返回true7.2 回溯失败的典型场景搜索 “ABCB”depth0: A(0,0), k0, A A ✓标记为0 depth1: B(0,1), k1, B B ✓标记为0 depth2: C(0,2), k2, C C ✓标记为0 depth3: 尝试找B - 右E(0,3): E ! B ✗ - 下C(1,2): 标记0已访问✗ - 左B(0,1): 标记0已访问✗ - 上越界 depth3全部失败恢复board[0][2]C 返回false depth2返回false恢复board[0][1]B depth1返回false恢复board[0][0]A 尝试其他起点...全部失败 返回false8. 易错点分析8.1 边界检查顺序错误写法intiiix,jjjy;if(dfs(ii,jj,k1))// 先递归再检查边界可能越界正确写法intiiix,jjjy;if(0iiiim0jjjjn){if(dfs(ii,jj,k1))// 先检查再递归}原因DFS内部会访问board[ii][jj]越界会导致未定义行为8.2 标记值的选取错误写法board[i][j]X;// 如果word包含X会出问题board[i][j]board[i][j];// 没有实际标记正确写法board[i][j]0;// 0不是字母可作为特殊标记8.3 回溯时机错误写法board[i][j]0;// 标记if(dfs(ii,jj,k1))returntrue;// 忘记回溯恢复returnfalse;后果其他分支无法使用该单元格导致漏解8.4 递归终止条件位置错误写法if(k1word.length())returntrue;if(board[i][j]!word[k])returnfalse;// 终止条件应该在匹配检查之后后果最后一个字符匹配后还会继续搜索8.5 外层循环遗漏错误写法// 没有从每个单元格作为起点枚举if(dfs(0,0,0))returntrue;// 只从(0,0)开始搜索后果如果word的第一个字符不在(0,0)位置会漏解9. 边界条件测试9.1 单单元格boardboard [[A]] word A -- true (正好一个字符) word AA -- false (字符不够)9.2 单行/单列boardboard [[A,B,C]] word ABC -- true (只能向右) word ACB -- false (不能向后走)9.3 word长度1board 任意 word A -- 只要board中有A就返回true9.4 word长度board面积board [[A,B],[C,D]] (4个单元格) word ABCDEF -- false (单元格不够用)9.5 全相同字符board [[A,A],[A,A]] word AAA -- true (可以从任意起点开始) word AAAA -- false (只有4个单元格)10. 面试追问 FAQ问题高分回答为什么用0标记而不是visited数组因为board中只有字母0不可能是任何字母可以作为天然的特殊标记节省O(M*N)空间如何进一步优化1) 先统计word和board的字符频率不匹配直接返回2) 使用Trie树优化多单词搜索3) 预计算每个字符的位置列表能处理word中有重复字符吗能因为每个单元格只能使用一次不是word中的字符不能重复使用如果board很大怎么办先检查board中是否包含word的所有字符或使用BFS剪枝或使用Trie预筛选回溯的本质是什么回溯是恢复现场让其他搜索路径可以使用被当前路径独占的单元格递归栈溢出怎么办word长度最多15不会溢出如果更长可改为显示栈模拟DFS和212题单词搜索II有什么区别212题是找所有存在于board中的单词需要TrieDFS本题只需判断一个单词是否存在11. 相关题目对比题号题目难度核心区别79单词搜索Medium判断单个单词是否存在212单词搜索 IIHard找出所有存在的单词需要Trie130被围绕的区域MediumDFS变体标记被围绕的’O’200岛屿数量MediumDFS遍历计数连通区域463岛屿的周长EasyDFS/BFS计算周长12. 总结要点详情算法深度优先搜索 回溯标记方法原地修改board用0标记已访问回溯时机递归返回前恢复现场剪枝策略字符不匹配立即返回找到解立即返回时间复杂度O(MN4^L)最坏指数级空间复杂度O(L)递归栈深度
