单词搜索II不能只用暴力DFS回溯，因为对每个单词单独DFS的时间复杂度高达O(wordsSize × m × n × 4^L)，易超时；而Trie+DFS可实时剪枝无效路径，并通过节点存储完整单词实现高效去重和结果收集。
为什么单词搜索II不能只用DFS暴力回溯
因为 board 上每个位置出发都可能生成大量无效前缀（比如 "zzz"），而字典里根本没这个词。纯 DFS 每次走到哪都得查一遍 words 数组，时间爆炸——O(MN × 4^L × W)，L 是路径长度，W 是单词数量。前缀树（Trie）的核心价值就是快速剪枝：走一步就查 Trie 当前节点有没有子节点，没有就立刻 return，避免后续无意义递归。
Trie 节点必须存 word 而不只是 is_end
单词搜索 II 要求返回所有匹配的单词，不是只判断存在性。如果 Trie 节点只设 is_end = true，DFS 到叶子时还得沿路径反向拼字符串（需要额外栈或 parent 指针），极不自然。正确做法是：在插入单词时，把完整单词存进叶子节点的 word 字段（或用指针指向原始字符串）。这样 DFS 一到达有效节点，直接 push 进结果即可。
常见错误：
- 插入时只标记 is_end，DFS 中靠递归参数拼接字符串 → 容易漏传、边界错、重复分配
- 多个单词共用同一路径（如 "app" 和 "application"），只在末尾存 word → 会漏掉短单词
- 忘记去重：同一个单词可能从不同起点/路径匹配多次 → 需在 Trie 节点中标记 used 或插入后清空 word
- 插入时：走到末尾节点，赋值
node->word = word - DFS 回溯中：一旦发现
node->word非空，就加入result，然后置为""（防重复） - 不要依赖
is_end做唯一判断，它只是辅助字段
DFS 过程中 Trie 指针怎么安全移动和回退
DFS 每步对应 board 上一个字符，也对应 Trie 当前节点的一个子节点。关键不是“保存路径”，而是“维护当前 Trie 节点指针”。每次进入新格子，用 board[r][c] 查 curr->children[ch - 'a']；若为空，直接 return；否则递归下去。回退时不需要“恢复 Trie 指针”，因为它是值传递（或局部变量），天然无副作用。
典型写法：
void dfs(vector<vector>>& board, int r, int c, TrieNode* node, vector<string>& res) {
char ch = board[r][c];
if (ch == '#' || !node->children[ch - 'a']) return;
<pre class="brush:php;toolbar:false;">node = node->children[ch - 'a']; // 移动到子节点
if (!node->word.empty()) {
res.push_back(node->word);
node->word = ""; // 去重
}
board[r][c] = '#'; // 标记已访问
for (int d = 0; d = 0 && nr = 0 && nc <p>}</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master"><img
src="https://img.php.cn/upload/skill/000/000/081/179051228971575.jpg" alt="C++ Code Review Master" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="overflowclass">C++ Code Review Master</a>
<p class="overflowclass">组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。</p>
</div>
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
注意：node 是传值或 const 引用，不是指针引用；node->children[...] 才是真正改变遍历位置的地方。
为什么 build Trie 后要剪枝（pruning）子树
当某个 Trie 节点被命中并收集了 word，它的所有后代节点其实已经“失效”——因为父路径已覆盖全部更长词（例如已找到 "app"，那 "apple" 就不该再被单独收集，除非题目要求所有前缀）。但更关键的是性能：如果不清空已匹配节点的子树，后续 DFS 可能反复进入同一分支做无用功。
实际中更常用的做法是：在收集 node->word 后，检查该节点是否为叶子（所有 children[i] == nullptr），若是，则向上回溯，把父节点对应 child 指针置空。但这实现复杂。简单有效的方式是——不做主动剪枝，而靠 node->word = "" + 后续 if (!node->word.empty()) 判断来跳过重复收集。真正影响性能的，是避免进入 nullptr 子节点，这点由 Trie 查询逻辑天然保证。
容易被忽略的一点：
- 如果字典极大（10⁵ 单词），Trie 构建后占用内存高，但 DFS 过程中不会 new/delete 节点，所以只要不爆栈，空间可控；
- board 大小通常远小于字典规模，因此 Trie 的深度受限于 board 最长可能路径（≤ MN），而非字典最长单词。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
