单词搜索经典题代码修复和解析

目录一、代码功能说明二、现有代码存在的问题 原因分析1. 核心 BUG最严重2. 起点位置未标记已访问3. 边界判断冗余不影响结果代码不优雅4. 特殊用例风险三、修复后的完整代码 逐行注释四、关键修复点总结五、算法整体流程梳理六、拓展小优化可选一、代码功能说明这是单词搜索经典题给定二维字符网格board和字符串word判断能否在网格中按上下左右相邻的顺序找出该单词每个单元格只能走一次。 整体思路遍历网格每个起点 DFS 深度优先搜索回溯。二、现有代码存在的问题 原因分析1. 核心 BUG最严重DFS 递归调用后没有接收返回值找到完整单词也不会向上传递结果永远返回false。// 错误写法调用了 dfs但没判断返回值 dfs(newX,newY,index1,visited,board,word);哪怕递归深处匹配成功return true上层也感知不到最终全部走到return false。2. 起点位置未标记已访问匹配第一个字符时没有把起点(i,j)标记为已访问会出现回头重复走起点的死循环 / 重复遍历。3. 边界判断冗余不影响结果代码不优雅visited和board行列一致重复判断长度。4. 特殊用例风险空字符串word未处理网格为空、单行 / 单列边界场景鲁棒性差。三、修复后的完整代码 逐行注释class Solution { public boolean exist(char[][] board, String word) { // 边界特判单词为空直接匹配成功 if (word null || word.length() 0) { return true; } int rows board.length; // 网格为空直接返回false if (rows 0) { return false; } int cols board[0].length; // 标记单元格是否已访问0未访问1已访问 int[][] visited new int[rows][cols]; // 遍历网格每一个位置作为DFS起点 for (int i 0; i rows; i) { for (int j 0; j cols; j) { // 找到单词第一个字符开始深度搜索 if (board[i][j] word.charAt(0)) { // 【修复1】起点先标记为已访问 visited[i][j] 1; if (dfs(i, j, 1, visited, board, word)) { return true; } // 回溯本轮起点搜索失败取消标记 visited[i][j] 0; } } } // 所有起点都尝试完毕未找到单词 return false; } /** * DFS 深度搜索 * param i 当前行 * param j 当前列 * param index 当前需要匹配的单词下标 * param visited 访问标记数组 * param board 字符网格 * param word 目标单词 * return 是否匹配成功 */ private boolean dfs(int i, int j, int index, int[][] visited, char[][] board, String word) { // 递归终止条件下标等于单词长度全部匹配完成 if (index word.length()) { return true; } // 上下左右 四个方向 int[][] dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int rows board.length; int cols board[0].length; for (int[] dir : dirs) { int newX i dir[0]; int newY j dir[1]; // 1. 越界判断 if (newX 0 || newX rows || newY 0 || newY cols) { continue; } // 2. 已访问过 或 字符不匹配跳过 if (visited[newX][newY] 1 || board[newX][newY] ! word.charAt(index)) { continue; } // 标记当前位置已访问 visited[newX][newY] 1; // 【修复2】接收递归返回值匹配成功直接向上返回true if (dfs(newX, newY, index 1, visited, board, word)) { return true; } // 回溯分支搜索失败撤销标记 visited[newX][newY] 0; } // 四个方向都走不通当前分支失败 return false; } }四、关键修复点总结传递递归结果核心修复把单纯调用dfs()改为if(dfs(...)) return true;让匹配成功的结果逐层向上返回。起点位置标记访问外层循环匹配首字符时先visited[i][j] 1搜索失败再回溯置 0防止重复走起点。代码优化合并越界、已访问、字符不匹配的判断逻辑更清晰增加空串、空网格的边界特判方向数组改用增强 for 循环可读性更强。五、算法整体流程梳理先做边界校验排除特殊空用例遍历网格每一个单元格若等于单词第一个字符作为搜索起点起点标记为已访问进入 DFS终止条件index 单词长度→ 全部匹配返回true遍历上下左右四个方向越界 / 已访问 / 字符不匹配 → 跳过合法且字符匹配 → 标记访问递归搜索下一个字符递归成功则直接返回true失败则回溯取消访问标记所有起点全部搜索完毕仍未匹配最终返回false。六、拓展小优化可选可以不用额外visited数组直接修改原网格做标记节省空间走过的字符临时改为#回溯时改回原字符 适合对空间复杂度要求高的场景逻辑不变。