212. 单词搜索 II（困难）

Blind 75 › 212. 单词搜索 II（困难） （第 3 章）
文章工具

题目

给定一个 m × n 的小写字母网格，和一个单词列表。请返回列表中所有能在网格上拼出来的单词。

拼写规则：从任意一格起步，每一步只能走到上下左右相邻的格子，按照经过的格子的字母依次组成单词；同一个格子在一个单词中只能使用一次。

自造示例：

board = [["c","a","t"],["o","d","g"],["n","a","e"]]，words = ["cat","dog","can","goat"] → ["cat","dog"]

"cat" 走 (0,0)→(0,1)→(0,2)，"dog" 走 (1,0)→(1,1)→(1,2)；"can" 中 a 到 n 不能斜着走、也不许复用格子，所以失败。也就是说，既要检查“字符序列走得到”，也要保证走法全程不重复使用格子。

约束：1 ≤ m, n ≤ 12；1 ≤ words.length ≤ 3 × 104；每个单词长度 1 ≤ word.length ≤ 10；所有字符均为小写英文字母；单词互不相同。

思路

一句话：把这么多单词建成一棵 Trie（前缀树），再让网格上的 DFS 一边走格子、一边沿着 Trie 向下走。

先想最直白的做法：对每个单词，都像“79. 单词搜索”那样，从每个格子出发做一次 DFS，搜到了就换下一个单词。这样外层要跑 3 × 104 次 DFS，而且 "app"、"apple"、"application" 这种共享前缀的单词，共同前缀会被反反复复搜很多遍，大量重复劳动。

稍好一点的做法：从每个格子出发，把所有长度不超过 10 的路径都枚举出来，再用单词集合做一次查询。这仍然有一个大问题——即使当前前缀已经不可能匹配任何一个单词，DFS 还是会执着地把这条路走到底。

关键观察：目标单词全部已知，它们的共同前缀是树状共享的。把 DFS 的“网格状态”和“字典前缀状态”绑定成 (格子, Trie 节点)：每到一个新格子，只看当前 Trie 节点有没有这个字母对应的子节点，没有就立刻剪枝。这样，不在任何候选词里的下一步当场放弃，共享前缀也只需要探索一次。

至于“同一个格子不能重复用”，沿用回溯的经典做法：进入时把格子临时改成 #，四个方向递归完再还原。

解法

用一棵 Trie 存全部单词：节点保存 children[26]，遇到完整单词时把整词保存在结束节点。然后遍历网格每个格子，以 root 为起点做带回溯 DFS。

阶段数据关键动作
建 Trie所有单词插入后，在终点节点记录完整单词
选起点每人格子 + root对每个 (i, j) 做一次 DFS
推进当前格子字符取 Trie 当前节点的对应子节点；不存在则剪枝
命中子节点保存的单词加入答案并清空该标记，避免同一词重复收集
回溯网格格子置 # 占位 → 四方向递归 → 还原原字符

到达一个单词终点后，只清掉“这是单词”的标记，而不删除节点，是为了让更长的同类词还能继续往下走。

下图把上面 5 个步骤串成流程，并逐步演示：

212. 单词搜索 II（困难） 解法步骤流程图
图① 解法步骤流程图（共 5 步）。
212. 单词搜索 II（困难） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
 TrieNode* root = new TrieNode();
 for (const string& w : words) {
 insert(root, w);
 }  int m = board.size(), n = board[0].size();
 vector<string> ans;
 for (int r = 0; r < m; ++r) {
 for (int c = 0; c < n; ++c) {
 dfs(board, r, c, root, ans);
 }
 }
 return ans;
 }  private:
 struct TrieNode {
 TrieNode* next[26] = {};
 string word;                    // 终点节点保存完整单词；空串表示不是终点
 };  void insert(TrieNode* root, const string& word) {
 TrieNode* node = root;
 for (char ch : word) {
 int idx = ch - 'a';
 if (!node->next[idx]) {
 node->next[idx] = new TrieNode();
 }
 node = node->next[idx];
 }
 node->word = word;
 }  void dfs(vector<vector<char>>& board, int r, int c, TrieNode* node, vector<string>& ans) {
 if (r < 0 || r >= (int)board.size() || c < 0 || c >= (int)board[0].size()) {
 return;
 }
 char ch = board[r][c];
 if (ch == '#') {
 return;
 }  TrieNode* nxt = node->next[ch - 'a'];
 if (!nxt) {
 return;                     // 当前前缀不属于任何候选词，剪枝
 }  if (!nxt->word.empty()) {
 ans.push_back(nxt-&g
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。