本文概览本文以LeetCode题目单词搜索为例讲解为什么用DFS不用BFS以及DFS在二维网格中的编写套路一、题目二、题目分析这题要求在二维网格中找单词有三个要求必须从单词的第一个字符开始字符必须上下左右相邻不能跳格子同一个位置的字符不能重复使用比如要找 “ABC”网格是A C B D E F这不算因为 A 的上下左右没有 BA 的右边是 C下边是 D所以无法组成连续的 “AB”。什么是连续就是每一步只能走到上下左右相邻的格子不能跳着走。思路概览Java 实现代码如下classSolution{privateintm,n;privateboolean[][]visited;privatefinalint[][]dirs{{0,1},{0,-1},{1,0},{-1,0}};publicbooleanexist(char[][]board,Stringword){mboard.length;nboard[0].length;visitednewboolean[m][n];for(inti0;im;i){for(intj0;jn;j){if(dfs(board,word,0,i,j)){returntrue;}}}returnfalse;}privatebooleandfs(char[][]board,Stringword,intindex,inti,intj){// 1. 所有字符匹配完毕直接成功优先于越界判断if(indexword.length()){returntrue;}// 2. 越界检查if(i0||im||j0||jn){returnfalse;}// 3. 已访问或字符不匹配if(visited[i][j]||board[i][j]!word.charAt(index)){returnfalse;}// 4. 标记当前格子visited[i][j]true;// 5. 向四个方向递归for(int[]dir:dirs){if(dfs(board,word,index1,idir[0],jdir[1])){visited[i][j]false;returntrue;}}// 6. 回溯visited[i][j]false;returnfalse;}}思路简要说明外层双重循环遍历每个格子作为起点调用 DFS 尝试匹配DFS 内部先判断出口匹配完成、越界、字符不匹配再标记当前格子向四方向递归最后回溯用一个visited数组记录已访问的格子回溯时恢复为false三、思路详解第一步为什么用 DFS 不用 BFS这题和前面的岛屿数量很像都是二维网格 四方向递归。岛屿数量用 DFS 或 BFS 都行但这题强烈推荐 DFS不推荐 BFS。为什么因为 BFS 需要记录每条路径的访问状态。举个例子假设从 A 出发走到 B 后有两条路路径1A → B → C → ... 路径2A → B → D → ...如果用 BFS队列里会同时存在这两条路径。路径1 访问了 C路径2 访问了 D它们的visited状态是不同的——路径1 不能再用 C路径2 不能再用 D但两条路径都不能用 A 和 B。如果用一个全局visited路径1 标记了 C路径2 就看不到 C 了但路径2 可能本来是可以走 C 的只是路径1 先走了。所以 BFS 要么给每个队列元素配一个独立的visited副本空间开销大要么用更复杂的状态记录方式代码复杂。而 DFS 就简单多了一个全局visited数组走到哪标记到哪走不通就回溯恢复。同一时刻只有一条路径在走visited状态天然就是当前路径的访问记录。第二步DFS 编写套路和岛屿数量对比这题的 DFS 框架和岛屿数量几乎一样// 岛屿数量的 DFSprivatevoiddfs(char[][]grid,inti,intj){if(越界||grid[i][j]0)return;grid[i][j]0;// 标记for(int[]dir:dirs){dfs(grid,idir[0],jdir[1]);}}// 单词搜索的 DFSprivatebooleandfs(char[][]board,Stringword,intindex,inti,intj){if(indexword.length())returntrue;// 匹配完成if(越界||visited[i][j]||board[i][j]!word.charAt(index))returnfalse;visited[i][j]true;// 标记for(int[]dir:dirs){if(dfs(board,word,index1,idir[0],jdir[1]))returntrue;}visited[i][j]false;// 回溯returnfalse;}区别在于岛屿数量单词搜索目标标记整个岛屿找到一条匹配路径标记方式直接改grid[i][j] 0用visited数组回溯不需要标记完就不管了需要走不通要恢复返回值voidboolean第三步递归出口的三个判断DFS 函数开头有三个判断顺序很重要// 1. 所有字符匹配完毕直接成功if(indexword.length()){returntrue;}// 2. 越界检查if(i0||im||j0||jn){returnfalse;}// 3. 已访问或字符不匹配if(visited[i][j]||board[i][j]!word.charAt(index)){returnfalse;}为什么index word.length()要放在最前面因为当index到达word.length()时说明所有字符都匹配完了此时i, j可能是越界的最后一个字符的下一个位置。如果先判断越界就会错误地返回false。举个例子单词 “AB”网格是A B匹配流程dfs(0, 0)board[0][0] A匹配标记递归dfs(0, 1)dfs(0, 1)board[0][1] B匹配标记递归dfs(0, 2)dfs(0, 2)index 2 word.length()返回true如果先判断越界dfs(0, 2)会因为j n返回false就错了。第四步标记 四方向递归 回溯匹配成功后标记当前格子向四方向递归visited[i][j]true;// 标记for(int[]dir:dirs){if(dfs(board,word,index1,idir[0],jdir[1])){visited[i][j]false;// 找到即返回也恢复一下returntrue;}}visited[i][j]false;// 回溯returnfalse;为什么要回溯因为当前路径走不通要退回去尝试其他路径。如果不恢复visited[i][j] false其他路径就看不到这个格子了。举个例子从 A 出发先往右走 B再往右走 C发现 C 的下一个字符不匹配回溯。此时 A 还要尝试往下走如果 B 没有被恢复A 往下走的路径就看不到 B 了虽然这条路径本来也不经过 B但visited状态是全局的。第五步完整执行过程以示例为例board [ [A, B, C, E], [S, F, C, S], [A, D, E, E] ] word ABCCED外层循环从(0, 0)开始board[0][0] A匹配word[0]开始 DFS。最终找到的路径在网格上长这样0 1 2 3 ┌───┬───┬───┬───┐ 0 │ A→│ B→│ C │ E │ ├───┼───┼───┼───┤ │ │ │ ↓ │ │ 1 │ S │ F │ C │ S │ ├───┼───┼───┼───┤ │ │ ← │ │ │ 2 │ A │ D │ E │ E │ └───┴───┴───┴───┘路径(0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1)对应字符 “ABCCED”。下面用表格展示每一步的状态变化步骤当前位置字符匹配 word 的哪个字符下一步尝试结果1(0,0)Aword[0]向右到 (0,1)继续2(0,1)Bword[1]向右到 (0,2)继续3(0,2)Cword[2]向右到 (0,3)E≠C失败回溯4(0,2)Cword[2]向下到 (1,2)继续5(1,2)Cword[3]向右到 (1,3)S≠E失败回溯6(1,2)Cword[3]向下到 (2,2)继续7(2,2)Eword[4]向右到 (2,3)E≠D失败回溯8(2,2)Eword[4]向左到 (2,1)继续9(2,1)Dword[5]index6word.length()成功注意第 3 步和第 4 步在 (0,2) 这个位置先尝试向右走发现不匹配回溯后再尝试向下走。这就是 DFS 的回溯机制——一条路走不通就退回来换一条路。第六步DFS vs BFS 对比DFSBFS数据结构递归栈队列visited一个全局数组每个路径需要独立副本回溯天然支持递归返回时恢复需要额外处理空间复杂度O(mn L)L 是单词长度O(mn × 路径数)代码复杂度简单复杂这题用 DFS 是标准做法BFS 虽然理论上可行但实现起来麻烦且效率低。四、总结这题和岛屿数量一样都是二维网格 四方向递归核心区别在于岛屿数量不需要回溯标记完就不管了单词搜索需要回溯走不通要恢复岛屿数量用 DFS 或 BFS 都行单词搜索强烈推荐 DFSBFS 的 visited 管理太复杂DFS 的编写套路判断出口匹配完成、越界、字符不匹配标记当前格子四方向递归回溯恢复这个套路适用于所有在网格中找路径的题目。
Hot 100 --- 单词搜索
本文概览本文以LeetCode题目单词搜索为例讲解为什么用DFS不用BFS以及DFS在二维网格中的编写套路一、题目二、题目分析这题要求在二维网格中找单词有三个要求必须从单词的第一个字符开始字符必须上下左右相邻不能跳格子同一个位置的字符不能重复使用比如要找 “ABC”网格是A C B D E F这不算因为 A 的上下左右没有 BA 的右边是 C下边是 D所以无法组成连续的 “AB”。什么是连续就是每一步只能走到上下左右相邻的格子不能跳着走。思路概览Java 实现代码如下classSolution{privateintm,n;privateboolean[][]visited;privatefinalint[][]dirs{{0,1},{0,-1},{1,0},{-1,0}};publicbooleanexist(char[][]board,Stringword){mboard.length;nboard[0].length;visitednewboolean[m][n];for(inti0;im;i){for(intj0;jn;j){if(dfs(board,word,0,i,j)){returntrue;}}}returnfalse;}privatebooleandfs(char[][]board,Stringword,intindex,inti,intj){// 1. 所有字符匹配完毕直接成功优先于越界判断if(indexword.length()){returntrue;}// 2. 越界检查if(i0||im||j0||jn){returnfalse;}// 3. 已访问或字符不匹配if(visited[i][j]||board[i][j]!word.charAt(index)){returnfalse;}// 4. 标记当前格子visited[i][j]true;// 5. 向四个方向递归for(int[]dir:dirs){if(dfs(board,word,index1,idir[0],jdir[1])){visited[i][j]false;returntrue;}}// 6. 回溯visited[i][j]false;returnfalse;}}思路简要说明外层双重循环遍历每个格子作为起点调用 DFS 尝试匹配DFS 内部先判断出口匹配完成、越界、字符不匹配再标记当前格子向四方向递归最后回溯用一个visited数组记录已访问的格子回溯时恢复为false三、思路详解第一步为什么用 DFS 不用 BFS这题和前面的岛屿数量很像都是二维网格 四方向递归。岛屿数量用 DFS 或 BFS 都行但这题强烈推荐 DFS不推荐 BFS。为什么因为 BFS 需要记录每条路径的访问状态。举个例子假设从 A 出发走到 B 后有两条路路径1A → B → C → ... 路径2A → B → D → ...如果用 BFS队列里会同时存在这两条路径。路径1 访问了 C路径2 访问了 D它们的visited状态是不同的——路径1 不能再用 C路径2 不能再用 D但两条路径都不能用 A 和 B。如果用一个全局visited路径1 标记了 C路径2 就看不到 C 了但路径2 可能本来是可以走 C 的只是路径1 先走了。所以 BFS 要么给每个队列元素配一个独立的visited副本空间开销大要么用更复杂的状态记录方式代码复杂。而 DFS 就简单多了一个全局visited数组走到哪标记到哪走不通就回溯恢复。同一时刻只有一条路径在走visited状态天然就是当前路径的访问记录。第二步DFS 编写套路和岛屿数量对比这题的 DFS 框架和岛屿数量几乎一样// 岛屿数量的 DFSprivatevoiddfs(char[][]grid,inti,intj){if(越界||grid[i][j]0)return;grid[i][j]0;// 标记for(int[]dir:dirs){dfs(grid,idir[0],jdir[1]);}}// 单词搜索的 DFSprivatebooleandfs(char[][]board,Stringword,intindex,inti,intj){if(indexword.length())returntrue;// 匹配完成if(越界||visited[i][j]||board[i][j]!word.charAt(index))returnfalse;visited[i][j]true;// 标记for(int[]dir:dirs){if(dfs(board,word,index1,idir[0],jdir[1]))returntrue;}visited[i][j]false;// 回溯returnfalse;}区别在于岛屿数量单词搜索目标标记整个岛屿找到一条匹配路径标记方式直接改grid[i][j] 0用visited数组回溯不需要标记完就不管了需要走不通要恢复返回值voidboolean第三步递归出口的三个判断DFS 函数开头有三个判断顺序很重要// 1. 所有字符匹配完毕直接成功if(indexword.length()){returntrue;}// 2. 越界检查if(i0||im||j0||jn){returnfalse;}// 3. 已访问或字符不匹配if(visited[i][j]||board[i][j]!word.charAt(index)){returnfalse;}为什么index word.length()要放在最前面因为当index到达word.length()时说明所有字符都匹配完了此时i, j可能是越界的最后一个字符的下一个位置。如果先判断越界就会错误地返回false。举个例子单词 “AB”网格是A B匹配流程dfs(0, 0)board[0][0] A匹配标记递归dfs(0, 1)dfs(0, 1)board[0][1] B匹配标记递归dfs(0, 2)dfs(0, 2)index 2 word.length()返回true如果先判断越界dfs(0, 2)会因为j n返回false就错了。第四步标记 四方向递归 回溯匹配成功后标记当前格子向四方向递归visited[i][j]true;// 标记for(int[]dir:dirs){if(dfs(board,word,index1,idir[0],jdir[1])){visited[i][j]false;// 找到即返回也恢复一下returntrue;}}visited[i][j]false;// 回溯returnfalse;为什么要回溯因为当前路径走不通要退回去尝试其他路径。如果不恢复visited[i][j] false其他路径就看不到这个格子了。举个例子从 A 出发先往右走 B再往右走 C发现 C 的下一个字符不匹配回溯。此时 A 还要尝试往下走如果 B 没有被恢复A 往下走的路径就看不到 B 了虽然这条路径本来也不经过 B但visited状态是全局的。第五步完整执行过程以示例为例board [ [A, B, C, E], [S, F, C, S], [A, D, E, E] ] word ABCCED外层循环从(0, 0)开始board[0][0] A匹配word[0]开始 DFS。最终找到的路径在网格上长这样0 1 2 3 ┌───┬───┬───┬───┐ 0 │ A→│ B→│ C │ E │ ├───┼───┼───┼───┤ │ │ │ ↓ │ │ 1 │ S │ F │ C │ S │ ├───┼───┼───┼───┤ │ │ ← │ │ │ 2 │ A │ D │ E │ E │ └───┴───┴───┴───┘路径(0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1)对应字符 “ABCCED”。下面用表格展示每一步的状态变化步骤当前位置字符匹配 word 的哪个字符下一步尝试结果1(0,0)Aword[0]向右到 (0,1)继续2(0,1)Bword[1]向右到 (0,2)继续3(0,2)Cword[2]向右到 (0,3)E≠C失败回溯4(0,2)Cword[2]向下到 (1,2)继续5(1,2)Cword[3]向右到 (1,3)S≠E失败回溯6(1,2)Cword[3]向下到 (2,2)继续7(2,2)Eword[4]向右到 (2,3)E≠D失败回溯8(2,2)Eword[4]向左到 (2,1)继续9(2,1)Dword[5]index6word.length()成功注意第 3 步和第 4 步在 (0,2) 这个位置先尝试向右走发现不匹配回溯后再尝试向下走。这就是 DFS 的回溯机制——一条路走不通就退回来换一条路。第六步DFS vs BFS 对比DFSBFS数据结构递归栈队列visited一个全局数组每个路径需要独立副本回溯天然支持递归返回时恢复需要额外处理空间复杂度O(mn L)L 是单词长度O(mn × 路径数)代码复杂度简单复杂这题用 DFS 是标准做法BFS 虽然理论上可行但实现起来麻烦且效率低。四、总结这题和岛屿数量一样都是二维网格 四方向递归核心区别在于岛屿数量不需要回溯标记完就不管了单词搜索需要回溯走不通要恢复岛屿数量用 DFS 或 BFS 都行单词搜索强烈推荐 DFSBFS 的 visited 管理太复杂DFS 的编写套路判断出口匹配完成、越界、字符不匹配标记当前格子四方向递归回溯恢复这个套路适用于所有在网格中找路径的题目。
