购物车中没有产品。
79. 单词搜索（中等）
Blind 75 › 79. 单词搜索（中等） （第 2 章）
题目
给定一个 m × n 的字符网格 board 和一个字符串 word，请判断：能不能从某个格子出发，每一步走到上下左右相邻的格子，让经过的字符依次拼成 word？每个格子只能被使用一次。
换句话说，问题是在网格图中找一条简单路径（不重复经过任何格子），使路径上的字符连起来恰好等于 word。
自造示例：设 board 为下面这个 3 × 3 网格。
| A | B | C |
| D | E | F |
| G | H | I |
word = "ABED" → true：路径 A(0,0) → B(0,1) → E(1,1) → D(1,0)。
word = "ABEDE" → false：走到 D 后再要 E，只能回到已用过的 E(1,1)，违反“不重复使用”。
约束：m == board.length，n == board[i].length，1 ≤ m, n ≤ 6；1 ≤ word.length ≤ 15；网格与单词仅含大小写英文字母。
思路
一句话：把“找单词”看成“在网格里走出一条不重复路径”，用 DFS 枚举路径，走不通就撤销当前这一步（回溯）。
最直白的想法：从每个格子出发，枚举所有能走的相邻方向，直到拼出单词或长度耗尽。但如果不做任何限制，每个格子在每一步最多有 4 个方向，一条长为 L 的路径最多产生 4L 种走法；再乘上 m·n 个起点，规模会爆炸。
好在题目给了两个很强的限制，都可以变成“剪枝”：
- 字符必须按顺序相等。 当前走到
word[i]时，下一步只需尝试那些值恰好等于word[i+1]的邻居；其它邻居直接剪掉。 - 同一格子不能重复使用。 当前路径就是递归栈：进入时把格子标记为“已使用”，离开时恢复。这样既保证不重复，也保证不同分支互不污染。
于是搜索树被压成：每个节点最多 4 个分支，去掉“来路”后实际上最多 3 个新分支；深度只有 L。题目 m,n ≤ 6、L ≤ 15，这个规模 DFS + 回溯完全可行。
为什么不能用贪心？因为某个局部匹配可能走向死胡同，必须能撤销刚才的选择，换另一个方向重试。例如某个格子有两个邻居都等于下一字符，先走其中一个可能失败；只有恢复该邻居、退回当前格子，才能再试另一个方向。这就是回溯的核心。
解法
核心就是 dfs(r, c, idx)：当前在 (r,c)，已经匹配到 word[idx]（下标从 0 开始），问能不能走完剩余部分。
- 先判非法：越界、字符不匹配、或已访问，直接返回
false。 - 若
idx已是最后一个字符，说明整串匹配完成，返回true。 - 把当前格子临时改成
'#'标记“本路径已使用”。 - 对上下左右四个邻居递归
dfs(nr, nc, idx + 1)，任一路径成功即返回true。 - 四个方向都失败后，把当前格子还原为原字符，再返回
false。
外层再枚举每个格子作为起点；只有 board[r][c] == word[0] 时才进入搜索。
以 word = "ABED" 为例：
| 已匹配下标 idx | 当前格子 | 动作 |
|---|---|---|
| 0 | A(0,0) | 起点，标记 A 已使用 |
| 1 | B(0,1) | 向右，标记 B 已使用 |
| 2 | E(1,1) | 向下，标记 E 已使用 |
| 3 | D(1,0) | 向左，恰好是末字符 → true |
如果某一步四个方向都不通，就恢复当前格子，返回上一层换方向；这保证了每个格子只属于当前这条路径。
下图把上面 5 个步骤串成流程，并逐步演示：
C++
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == word[0] && dfs(board, word, 0, i, j)) {
return true;
}
}
}
return false;
} private:
bool dfs(vector<vector<char>>& board, const string& word,
int idx, int r本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。
还没有评论，来说两句？