知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 08 - 单词搜索 ## 题目(LeetCode 79) 给定一个二维字符网格 board 和一个字符串 word,判断 word 是否存在于网格中。单词必须由相邻单元格(上下左右)的字母构成,同一个单元格不能重复使用。 ``` board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]] word = "ABCCED" → true(A→B→C→C→E→D) word = "SEE" → true(S→E→E) word = "ABCB" → false(B 不能重复用) ``` ## 大白话理解 在一个字母方阵里找单词,像贪吃蛇一样走,每一步只能上下左右移动,走过的格子不能再走。 从每个格子出发,尝试匹配单词的第一个字母。匹配上了就往四个方向继续找第二个字母,以此类推。走不通就退回来换方向。 ## 代码 ```java class Solution { public boolean exist(char[][] board, String word) { int m = board.length, n = board[0].length; //字符串可以从任何位置开始,所以从任何位置开始遍历 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (backtrack(board, word, i, j, 0)) return true; } } return false; } private boolean backtrack(char[][] board, String word, int row, int col, int index) { // 所有字符都匹配完了 if (index == word.length()) return true; // 越界或字符不匹配 if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != word.charAt(index)) { return false; } // 标记当前格子为已访问(用特殊字符替换,省去 visited 数组) char temp = board[row][col]; board[row][col] = '#'; // 向四个方向探索 boolean found = backtrack(board, word, row + 1, col, index + 1) || backtrack(board, word, row - 1, col, index + 1) || backtrack(board, word, row, col + 1, index + 1) || backtrack(board, word, row, col - 1, index + 1); // 撤销标记(回溯) board[row][col] = temp; return found; } } ``` > 💬 **Q:这里为什么要暂时替换掉?** > > 这是"原地标记已访问"的技巧,替代额外的 `visited` 数组。**核心目的:防止同一条路径上重复走同一个格子。** > > ``` > board: 搜索 "ABCCED",当前路径 A(0,0)→B(0,1)→C(0,2) > A B C > S F C 如果不标记,从 C(0,2) 向左探索时会走回 B(0,1) > A D E B 还是 'B',和 word[3]='C' 不匹配虽然这次没问题 > 但如果 word 里有重复字母,就会出现同一格子走两次的错误 > > 把 board[0][2] 改成 '#' 后: > 从 C(0,2) 向左探索 B(0,1),发现是 'B' 不等于 word[3]='C',返回 > 向上越界,向右越界,向下探索 F(1,2)... > 不会走回已经走过的格子 ✓ > ``` > > **为什么用 `#` 而不是 `boolean[][] visited`?** > > 效果完全一样,但省了一个 m×n 的额外数组。用 `#` 是因为题目保证输入只有字母,`#` 不会和任何字母冲突。 > > **为什么探索完之后要恢复(`board[row][col] = temp`)?** > > 因为这条路径探索失败后,要回溯去试其他路径。其他路径可能也需要经过这个格子,所以必须还原: > > ``` > 搜索 "SEE",从 S(1,0) 出发: > → 向右走 F(1,1),F≠E,失败,回溯 > → 向下走 A(2,0),A≠E,失败,回溯 > → 向上走 A(0,0),A≠E,失败,回溯 > → 最终找到 S→E(2,2)→E(2,3) 这条路 > > 如果 S 被标记后不恢复,后续所有从 S 出发的路径都断掉了,找不到答案 > ``` ### 逐行拆解 ``` backtrack(board, word, row, col, index) 的含义: 从 (row, col) 出发,能否匹配 word[index..end] 终止条件: index == word.length() → 全部匹配成功 越界 / 字符不匹配 → 此路不通 标记已访问: 把当前格子改成 '#',这样后续递归不会重复走 回溯时恢复原值 四个方向: 上下左右各试一次,有一个方向成功就返回 true || 短路运算:找到一个就不再继续 ``` ### 为什么不用 visited 数组? 直接修改 board 本身作为标记,省空间。把当前字符改成 `#`(或任何不会出现的字符),回溯时改回来。效果和 visited 数组一样。 ## 画图模拟 ``` board: word: "ABCCED" A B C E S F C S A D E E 从 (0,0) 开始,board[0][0]='A' == word[0]='A' ✓ 标记 (0,0) 为 '#' 往右 (0,1)='B' == word[1]='B' ✓ 标记 (0,1) 为 '#' 往右 (0,2)='C' == word[2]='C' ✓ 标记 (0,2) 为 '#' 往下 (1,2)='C' == word[3]='C' ✓ 标记 (1,2) 为 '#' 往下 (2,2)='E' == word[4]='E' ✓ 标记 (2,2) 为 '#' 往左 (2,1)='D' == word[5]='D' ✓ index=6 == word.length → 返回 true ✓ ``` ## 复杂度 - 时间:O(m × n × 3^L),L 是单词长度,每步最多 3 个方向(不能回头) - 空间:O(L),递归深度 ## 一句话总结 网格 DFS + 回溯。从每个格子出发,四个方向探索,用原地修改代替 visited 数组。 --- 上一篇:[07 - N 皇后](./07-n-queens.md) | 下一篇:[09 - 括号生成](./09-generate-parentheses.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入