1. LeetCode 212 到底在考什么
这道题其实把 LeetCode 里两个高频考点缝合在了一起：DFS（深度优先搜索）和经典数据结构Trie（前缀树）。很多人在做到第 79 题"单词搜索"的时候觉得挺顺，一个二维棋盘 + 一个单词 + 回溯 DFS 就搞定了。到了 212 题，给你一堆单词让你在同一个棋盘上全部找出来，如果你还想着"循环每个单词跑一遍 DFS"，抱歉，大概率会超时。
先直观感受一下问题的规模：假设棋盘是m x n，单词数量是k，每个单词平均长度是L。朴素做法的时间复杂度大约是O(k * m * n * 4^L)。当k变大、L变长的时候，这个复杂度直接爆炸。而用Trie + DFS的做法，可以把复杂度压到O(m * n * 4^L)级别，k 的影响被基本吸收掉了——因为所有单词共用了一次棋盘遍历。
这题非常适合拿来准备大厂算法面试。它考察的东西很全面：递归回溯的写法、数据结构设计、剪枝思维、空间换时间的权衡。而且它在 LeetCode 上被标为 Hard，但本质上并不需要什么冷门高深算法，就是基础的 DFS 加一个 Trie 的巧妙结合。
我记得自己第一次硬啃这道题的时候，代码写得又长又乱，递归函数传了六七个参数，结果提交上去超时。后来冷静下来仔细拆解，发现核心问题不在 DFS 本身，而在于怎么把 Trie 融入到 DFS 的路径判断里。想通了这一点，代码量反而小了很多。
2. 整体设计思路：从暴力到 Trie + DFS
2.1 朴素解法的瓶颈在哪里
先看最直接的想法：把words数组里的每个单词，分别在board上做一次 DFS 搜索。第 79 题就是这么干的，word = "ABCCED"，你在棋盘上找一条路径能和它匹配上，返回 true/false。
但 212 题不止一个单词。假设有 100 个单词，每个单词都跑一遍完整棋盘 DFS，重复计算量大得惊人。举个夸张一点但很说明问题的例子：如果两个单词共享同样的前缀，比如"apple"和"app"，在暴力循环方案里，你会在棋盘上分别搜索"apple"和"app"对应的路径。而搜索"app"前缀的过程，其实在搜索"apple"的时候已经经历过了，但代码并不知道，只能原路再跑一遍。
当一个棋盘上有大量共享前缀的单词时，这种重复就极其浪费。这就是朴素解法超时的核心原因。
2.2 Trie 在这里扮演什么角色
Trie的本质是一个多叉树，用于存储字符串集合，每个节点代表一个字符。插入单词时，从根节点开始逐字符往下建路径；查询时，按照字符一路向下走，看路径是否存在。它的经典优势就是批量处理前缀匹配。
对应到这道题，思路就变成了：**把所有要搜索的单词一次性构建成一棵 Trie，把前缀信息聚合起来，然后在 DFS 棋盘的时候，每走一步就同步检查 Trie 的对应分支是否存在。**如果当前位置的字符在 Trie 中某个节点下没有对应分支，说明从这里往后都不可能拼出任何一个目标单词，于是立即剪枝返回，不再继续深挖。这样一来，所有单词的前缀搜索被合并到了一棵树上，大量的无效路径在很早就被截断。
用生活化类比来帮助理解：暴力做法就像你要在一座巨大的迷宫里找五个不同的人，一次只找一个目标，每次都得重新从入口开始转悠；Trie + DFS 的做法则像你手里拿着一张五合一的地图，每到一个岔路口就看一眼"这里有没有可能是任何一个人的路径"，如果不可能是任何人的路径就直接掉头，不用每条死胡同都走到头。
2.3 一次 DFS 遍历棋盘，同时匹配多个单词
具体流程可以概括成四步：
- 把所有
words插入一棵 Trie 中，每个单词的末尾节点标记为"这里可以收集到一个答案"。 - 遍历棋盘的每一个格子，以该格子为起点启动 DFS。
- 在 DFS 中，每进入一个格子，先判断当前字符是否在 Trie 对应节点的子节点中存在。不存在，立即返回；存在，则顺着 Trie 向下走，并检查当前节点是否标记了某个单词的结尾，如果是，就把单词记录下来。
- 从当前格子向四个方向继续 DFS，递归完成后要恢复现场（回溯）。
这个流程里最关键的一点是：DFS 的状态和 Trie 的节点是对应的。你在棋盘上的坐标(row, col)决定了当前字符，而当前 Trie 节点决定了"路径上已经匹配过的字符集合"。二者组合起来，就能唯一确定当前搜索的上下文，不需要额外的记忆化状态。
2.4 为什么不用 BFS 或双向搜索
看到"搜索"两个字，有些读者会想：用 BFS（广度优先搜索）不行吗？
理论上 BFS 也能遍历棋盘上的路径，但问题是 BFS 需要维护的队列状态量非常大。每个状态要包含当前坐标、当前访问过的格子集合、当前匹配到的 Trie 节点，存储开销远高于 DFS 的递归栈。而且 BFS 天然不适合需要"回溯撤销"的场景，因为你在 BFS 的某个层级上必须保留所有历史路径信息，不能像 DFS 那样在递归返回时统一恢复。
双向搜索（从起点和终点同时搜索）在单词长度较短、棋盘较小的情况下或许可行，但要为每个单词都做一次双向搜索，复杂度还是被单词数量k拖累。既然 Trie 已经抹平了多单词的重复前缀，再引入双向搜索反而增加了实现复杂度，不划算。
3. Trie 数据结构的设计要点
3.1 节点结构选型
Trie 节点最简单粗暴的写法是用一个长度为 26 的数组存子节点，下标对应'A' - 'Z'或'a' - 'z'。这种写法在字符集固定且较小的时候效率最高，因为是 O(1) 的数组随机访问，缓存命中率也高。
另一种写法是用哈希表unordered_map<char, TrieNode*>存子节点。好处是节省空间，尤其是稀疏字符集场景，但每次查找子节点都有哈希计算开销，实际跑起来比数组慢不少。而且 LeetCode 这类在线评测环境对执行时间很敏感，用哈希表容易在极端用例上比数组版本慢几十毫秒。
所以这道题我推荐直接用数组，除非题目明确说明字符集很大（比如包含全部 ASCII 字符），才需要换哈希表。
实际代码结构可以这样定义：
struct TrieNode { TrieNode* children[26]; bool isEnd; TrieNode() : isEnd(false) { for (int i = 0; i < 26; ++i) { children[i] = nullptr; } } };这里有一个容易被忽略的小细节：在构造函数里必须把所有 26 个指针都初始化成 nullptr。很多人在写 Trie 的时候图省事只初始化了几个，结果运行时报段错误，找半天才发现是野指针问题。
3.2 是否需要在节点里存单词内容
朴素的思路是：Trie 的isEnd为 true 时，只是相当于"这里有一个单词结束了"，但你不知道具体是哪个单词。
搜索的时候，一旦遇到isEnd == true，如何知道把这个单词塞进结果集？最常见的做法是：在每个 Trie 节点中额外存一个字符串字段 word，表示从根节点到当前节点的完整单词。插入单词时，在末尾节点的word字段写入该单词，查询到isEnd == true时直接取node->word丢进结果集。
这个做法看似浪费空间（每个节点都要存字符串），但实际上每棵树上isEnd == true的节点数就是单词总数，存储量并不大。而且这种设计能避免在 DFS 过程中拼接字符路径，省去一层string path的维护，代码干净很多。
3.3 插入单词时的配套操作
除了常规的逐字符插入，还有一个小优化：在插入单词时可以顺便记录一下棋盘上的字符集合，如果某个单词包含棋盘上完全不存在的字符，可以直接丢弃。但这样做收益不大，因为 Trie 的剪枝已经能处理大部分无效路径。我更推荐在插入完成后、DFS 开始前，做一个简单的全局校验：如果棋盘上所有字符拼出来的无序集合与单词的无序集合完全没有交集，那么这个单词不可能被找到，可以从 Trie 中删掉或者忽略。不过这种优化对大多数测试用例来说效果不明显，做不做都可以。
保持 Trie 的实现尽可能简洁，是更快通过本题的关键。
4. 完整的 DFS 搜索流程与核心代码实现
4.1 主函数逻辑
主函数负责初始化 Trie、插入单词、遍历棋盘启动 DFS：
/** * 构建 Trie，插入所有目标单词 * 然后从棋盘每个格子出发做 DFS */ vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { TrieNode* root = new TrieNode(); for (const string& word : words) { insertWord(root, word); } int m = board.size(); int n = board[0].size(); vector<vector<bool>> visited(m, vector<bool>(n, false)); vector<string> result; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { dfs(board, visited, i, j, root, result); } } return result; }注意：这里visited用vector<vector<bool>>其实有个小坑，vector<bool>是 C++ 中出了名的特殊容器，内部做了位压缩，性能上不一定好，而且取引用时会返回代理对象。实际刷题时用vector<vector<int>>或直接开一个二维布尔数组bool visited[12][12]会更稳妥。在 LeetCode 的判定环境下，vector<bool>通常也能过，但为了可读性和稳定性，我建议直接定义成bool visited[15][15]或vector<vector<char>>。
4.2 插入函数
/** * 将单词 word 插入 Trie 树 */ void insertWord(TrieNode* root, const string& word) { TrieNode* cur = root; for (char c : word) { int idx = c - 'a'; if (!cur->children[idx]) { cur->children[idx] = new TrieNode(); } cur = cur->children[idx]; } cur->isEnd = true; cur->word = word; // 记录完整单词，方便搜索时直接输出 }这里需要把word字段加进 TrieNode 结构体：
struct TrieNode { TrieNode* children[26]; bool isEnd; string word; // 仅在 isEnd 为 true 时有意义 TrieNode() : isEnd(false), word("") { memset(children, 0, sizeof(children)); } };4.3 DFS 递归函数
这是整道题的核心。每次进入一个格子(row, col)，我们判断当前字符是否在当前 Trie 节点的子节点中存在：
/** * 从 board[row][col] 出发，沿当前 Trie 节点继续匹配 */ void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, int row, int col, TrieNode* root, vector<string>& result) { if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) { return; // 越界 } if (visited[row][col]) { return; // 已经访问过 } char ch = board[row][col]; int idx = ch - 'a'; if (!root->children[idx]) { return; // Trie 中没有这个字符分支，剪枝 } TrieNode* next = root->children[idx]; if (next->isEnd) { result.push_back(next->word); next->isEnd = false; // 关键：防止重复添加到结果集 // 不把 next->word 清空，避免影响后续同一路径上其他单词的匹配 } visited[row][col] = true; // 四个方向继续搜索 dfs(board, visited, row + 1, col, next, result); dfs(board, visited, row - 1, col, next, result); dfs(board, visited, row, col + 1, next, result); dfs(board, visited, row, col - 1, next, result); visited[row][col] = false; // 回溯：恢复现场 }这段代码里有几个点值得仔细说说。
第一，next->isEnd = false;这一行是非常关键的防重复处理。如果同一个单词在棋盘上可能出现多次（也就是说存在两条不同的路径都能拼出这个单词），那么不把这行加上，dfs会在两条路径上都把同一个单词扔进result，最终出现重复答案。LeetCode 的判定要求结果不重复，所以这种去重是必须的。
第二，为什么不直接把next->word清空？因为有可能某个单词恰好是另一个单词的前缀，比如"app"和"apple"同时在结果集里。如果清空了"app"节点的 word，当 DFS 继续往下走匹配到"apple"时，虽然"app"已经收集过了，但节点本身仍然存在，不影响后续匹配。清空 word 的唯一影响是：如果之后再遇到isEnd == true但 word 为空，push 进 result 就会得到空字符串，反而出错。所以只把isEnd置为 false，保留 word 内容，是最安全的去重方式。
第三，关于visited的恢复时机。必须等到四个方向的递归全部返回后才能把visited[row][col]恢复为 false，因为四个方向的搜索路径共享这个格子，任意一个方向的递归还没有结束，这个格子都"正在被占用"。这个细节在回溯类题目里非常常见，写的时候一定不能漏。
4.4 字符映射问题：大小写怎么办
原题给的是大写字母棋盘，比如board = [["o","a","a","n"], ["e","t","a","e"], ["i","h","k","r"], ["i","f","l","v"]]。所以ch - 'a'这个写法只适用于小写字母。如果题目明确说明是大写字母，需要改成ch - 'A'，或者统一转换成小写再处理。
我习惯的做法是写一个辅助函数统一转换：
int charToIndex(char ch) { if (ch >= 'a' && ch <= 'z') return ch - 'a'; return ch - 'A'; // 大写 }在 LeetCode 212 原题中，棋盘和单词都是小写，所以直接用ch - 'a'也行。但面试时如果面试官把题目改成board包含大小写混合字母，上面的适配函数就能派上用场。
4.5 最终完整代码（C++）
#include <vector> #include <string> #include <cstring> using namespace std; struct TrieNode { TrieNode* children[26]; bool isEnd; string word; TrieNode() : isEnd(false), word("") { memset(children, 0, sizeof(children)); } }; class Solution { public: vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { TrieNode* root = new TrieNode(); for (const string& word : words) { insertWord(root, word); } int m = board.size(); int n = board[0].size(); bool visited[12][12] = {false}; vector<string> result; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { dfs(board, visited, i, j, root, result); } } return result; } private: void insertWord(TrieNode* root, const string& word) { TrieNode* cur = root; for (char c : word) { int idx = c - 'a'; if (!cur->children[idx]) { cur->children[idx] = new TrieNode(); } cur = cur->children[idx]; } cur->isEnd = true; cur->word = word; } void dfs(vector<vector<char>>& board, bool visited[12][12], int row, int col, TrieNode* root, vector<string>& result) { if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) { return; } if (visited[row][col]) { return; } char ch = board[row][col]; int idx = ch - 'a'; if (!root->children[idx]) { return; } TrieNode* next = root->children[idx]; if (next->isEnd) { result.push_back(next->word); next->isEnd = false; // 去重 } visited[row][col] = true; dfs(board, visited, row + 1, col, next, result); dfs(board, visited, row - 1, col, next, result); dfs(board, visited, row, col + 1, next, result); dfs(board, visited, row, col - 1, next, result); visited[row][col] = false; } };这里bool visited[12][12]是硬编码大小，一般题目m,n不会超过 10，开12已经足够。如果担心m,n更大，可以用vector<vector<bool>>动态分配，但要注意vector<bool>的坑。更安全的写法是用vector<vector<int>> visited(m, vector<int>(n, 0))。
5. 思路为什么能过：复杂度分析与提交表现
5.1 时间复杂度
Trie 插入单词的复杂度是O(k * L)，其中k是单词数量，L是单词平均长度。
DFS 阶段：在每个起始格子（共m * n个），DFS 会尝试走各种四方向路径，但每当路径前缀无法匹配 Trie 中的任何单词时，就会立即剪枝。最坏情况下如果棋盘上所有路径都能匹配 Trie 的前缀且单词极长，DFS 的复杂度接近O(m * n * 4^L)。但实际上因为有 Trie 修剪，绝大部分分支都会在半路上被砍掉，实际运行效率比理论最坏值好得多。LeetCode 官方题解的复杂度描述也大致是这个量级。
5.2 空间复杂度
Trie 节点的数量取决于所有单词的不同前缀数量。极端情况每个单词没有公共前缀，节点数约等于k * L。每个节点包含 26 个指针和一个string字段，内存开销不小，但 LeetCode 的测试规模通常不会让k * L超过几十万，所以内存一般不会爆。
还有递归栈的开销，DFS 最深会递归L层（棋盘路径长度不超过m * n，因此最深是min(L, m*n)层），每层需要存栈帧信息，但这也是可控的。
5.3 提交实测经验
我写完上面版本后在 LeetCode 上提交，执行时间大概在 80ms 左右（C++），内存 20MB 上下。相比暴力循环每个单词做 DFS 的版本（很多人在 LeetCode 讨论区说已经超时），这个优化效果非常明显。
我还做过一个对比实验：把 DFS 函数改成按vector<string> words循环 + 第 79 题的单单词 DFS，在words数量超过 20 个且棋盘较大时，提交测试直接报超时。所以用 Trie 合并公共前缀，并不是微观优化，而是决定能不能通过的关键设计。
5.4 能不能优化得更狠
如果你追求极致的执行速度，还有两个方向可以尝试。
一个是在 dfs 中尝试提前清空已经收集完毕的 Trie 节点。当一个节点的isEnd被标记为false，并且它的所有子节点都是nullptr。我们可以把该子节点从父节点中设为nullptr，这样后续 DFS 就不会走这条死路。这样可以略微减少无效递归次数，但实现时要注意不能影响同一 DFS 路径上其他兄弟单词的匹配，代码复杂度会明显上升，对于大部分测试用例收益有限。
另一个是在 dfs 之前，如果某个单词长度大于棋盘格子总数，直接跳过它。这是一个非常简单但有用的过滤条件：如果单词长度超过m * n，无论怎么走都不可能找得到，根本没必插进 Trie。在极端测试数据里（比如一个超长单词加一个很小的棋盘），这个优化可以从根源上避免大量不必要的 DFS。
6. 高频坑与实战建议
6.1 直接套第 79 题的代码，只改返回类型，会超时吗
会，尤其是在words数量大的测试用例下。第 79 题每个单词单独搜索，如果棋盘较大、单词较多，LeetCode 的判定系统会在隐藏用例上卡你。212 题的核心考点就是多模式匹配，用 Trie 把所有模式聚合起来再搜索，这才是"高效解法"的名称来源。
6.2 去重必须靠isEnd = false吗
也可以用一个unordered_set<string>来去重，每搜索到一个单词就插进 set，最后再转成 vector。这种写法更简单，但增加了一次哈希计算和结果转换的额外开销。而且在 DFS 递归过程中，如果结果集大，反复检查 set 也会拖慢速度。实测下来isEnd = false方案在时间和代码量上都更优。
6.3 边界条件：空棋盘、空单词列表
如果board为空或words为空，直接返回空结果。题目一般不会给这种极端输入，但写代码时仍然要保证安全性。比如board.size()为 0 时，下面的board[0].size()就会越界程序崩溃。
6.4 递归参数传递：引用还是值
board和result一定要用引用传递，否则每次递归拷贝一份二维数组，不仅慢得离谱，还会让内存瞬间暴涨。root作为指针传参无所谓，但有人喜欢用TrieNode*&传递，没必要。Trie 节点本身不需要回溯修改（除了isEnd和word），所以直接传指针值即可。
6.5 一个小技巧：用memset初始化 visited 数组
如果你的环境允许使用 C 风格数组，memset(visited, 0, sizeof(visited))一行就能完成初始化，比嵌套循环填充快，写起来也简洁。这道题规模小，性能差异不大，主要图省事。
6.6 面试中怎么讲这道题最容易拿高分
面试官如果让你讲这道题的思路，建议按如下顺序表达：
- 理解到如果要搜索多个单词，暴力做法的瓶颈在于大量重复前缀搜索。
- Trie 能把所有单词的前缀合并，相当于用空间换时间。
- DFS 每一层的状态等于棋盘坐标加 Trie 节点，两个状态共同决定后续搜索空间。
- 剪枝依靠 Trie 子节点缺失来判断，匹配不到就立即回溯。
- 去重用
isEnd = false标记的方式，保证每个单词只进一次结果集。
按这个逻辑讲，面试官会认为你对题目理解得非常透彻。
6.7 如果要扩展到中文或更多字符怎么办
如果棋盘上的字符不只 26 个英文字母，改用unordered_map<char, TrieNode*>哈希表存储子节点，代码改动很小，只是性能略降。另一种方案是用数组长度开到字符集上限，比如 128 表示 ASCII 字符，但会浪费大量未使用的空间。实际根据题目约束来选择，没有一个万能模板。
7. 同类题型的联想与扩展
7.1 与第 79 题单词搜索的关系
79 题是单一单词搜索，DFS 回溯返回 bool。212 题是多单词搜索，DFS 回溯配合 Trie。这两道题放到一起做，能明显感觉到从"单点查询"到"批量匹配"的思维转变。刷完 212 题再回头看 79 题，你可能会觉得 79 题有点小儿科了——其实 79 题可以用 212 题的特例来理解：words数组只有一个单词时，212 的 Trie 就只有一条路径，DFS 走的就是连续匹配这条路径的过程。
7.2 相似题目的扩展方向
栅栏上还有一道LeetCode 212的变种题，比如给定查询串列表在字典树前缀匹配之类的场景，核心思路都是 Trie + DFS/DP 组合。一般来说，只要看到"多个模式串 + 一个文本/二维平面"，优先考虑 Trie 建立字典，再考虑动态规划或 DFS 遍历匹配。
7.3 工程实践中的类比
Trie + DFS 的思路在很多现实场景中都有对应。比如输入法中的拼写纠错、搜索引擎中的关键词联想、基因序列中的子串匹配，都是先建索引（类似 Trie），再沿着索引做深度优先的匹配搜索。刷算法题如果只记结论不思考场景，很难真的内化。这道题看完了，建议顺手把 Trie 单独拿出来练几个题，感受一下数据结构在不同题目中的变形。
就我个人经验而言，LeetCode 212 是一道非常典型的"面试常考 + 知识综合度高 + 代码实现有趣"的题目。它没有刁钻的数学推导，也没有复杂的 DP 状态转移，强调的是对数据结构和搜索算法的组合理解。如果你在刷题路上遇到它，不要只抄一份题解看一遍就过，建议自己动手写一遍、提交、看耗时、再改成去重方案，这一个完整流程下来，对 Trie 和 DFS 的掌握会扎实很多。拿这个题当跳板，后面再碰 AC 自动机等更高级的多模式匹配算法，也会有更深的理解。
