企业官网建设流程全解析

项目标题: 212. 单词搜索 II（Word Search II）— C语言 Trie + DFS 高质量题解

很多刷 LeetCode 的朋友应该都有这种感觉：Hard 题不一定算法多高深，但一定很考验“组合能力”。单词搜索 II 就是典型代表，它把二维网格 DFS 和前缀树 Trie 揉在一起，考察的是 79 题“单词搜索”的进阶版，同时也是面试里出现频率很高的一道题。这两天我用 C 语言重新实现了一遍，把 Trie + DFS 的完整思路、代码细节、剪枝技巧整理了一下，顺便记录几个我踩过的坑。如果你正在准备算法面试，或者想用 C 语言练一练指针、递归和二维数组操作，这篇内容应该对你很有帮助。

这题要解决的核心问题是：给你一个m x n的字符网格和一个单词列表words，找出所有同时存在于网格和单词列表中的单词。搜索时可以从任意格子出发，只能走上下左右四个方向，同一个格子在一个单词的构造过程中不能重复使用。暴力解法是拿每个单词分别去网格里 DFS，单词一多、网格一大就很容易超时。更聪明的做法是先把所有单词塞进一棵 Trie，然后对整个网格做一次 DFS，在搜索过程中同步匹配整棵 Trie，这样可以把大量重复前缀的搜索全部省掉。

1. 题目拆解与思路演进

1.1 从“单词搜索”到“单词搜索 II”的思维升级

先说说 79 题“单词搜索”。那题只给一个单词，做法很直观：遍历网格里每一个格子，从当前格子出发，上下左右递归扩展，维护一个 visited 数组防止重复使用格子，如果某个方向能匹配到单词结尾，就返回 true。整个搜索路径像一条蚯蚓在网格里爬，剪枝条件就是“下一步字符必须等于目标单词的下一个字符”。

212 题如果把同一个思路复制过来，就是每个单词跑一遍完整的 DFS。比如words = ["oath","oats","oat"]这三个单词，它们共享"oat"这个前缀，暴力做法会分别从'o'开始走三遍完全一样的前缀路径。网格稍微大一点、单词数量再多一点，时间消耗就直接起飞了。

所以这题的核心诉求其实是：能不能把多个单词的搜索过程合并到一次遍历里？答案就是前缀树。提前把所有单词建进一棵 Trie，当 DFS 走到某个格子时，只需要检查当前字符对应的 Trie 子树是否存在；如果不存在，说明从起点到这个格子的路径不可能是任何单词的前缀，直接剪枝；如果走到了某个标记为“单词结尾”的 Trie 节点，说明网格中存在该单词，收集结果。

1.2 暴力法到底慢在哪

假设网格大小是8 x 8，一个单词长度是L=10，每次从起点出发，最坏情况下每个位置有 4 个方向可以尝试，暴力 DFS 单个单词的时间上界是O(M * N * 4^L)。4^10大约是一百万，再乘上 64 个格子，单次搜索就到千万级。如果words有 200 个单词，最坏情况就是200 * 64 * 4^10，这个量级在普通 OJ 上基本跑不动，更不用说 LeetCode 的测试用例往往是把网格和单词列表都拉满了。

有人可能会说：那我可以给每个单词做个前缀预判，但本质上还是在重复扫描公共前缀。前缀重叠越多，浪费越严重。Trie 的思路就是把“重复扫描公共前缀”这部分开销彻底变成一次建树成本，后面网格遍历时，公共前缀路径只需要走一次。

1.3 为什么 Trie 是这种多模式匹配场景的天然数据结构

Trie 又叫前缀树、字典树，它的核心特点是把字符串集合按前缀组织成一棵树。根节点不存字符，从根节点到任意节点的路径对应一个字符串的前缀，每个节点的子节点代表下一个字符。

放在单词搜索 II 里，这个特性简直是为网格 DFS 量身定做的。DFS 每深入一格，就相当于在 Trie 中下探一层。当前路径在网格里延伸时，如果 Trie 中对应节点没有某个方向的子节点，那这条路就根本不用走，直接剪掉。这种剪枝不是靠业务规则，而是数据结构天然带来的，所以效率非常高。

还有一个细节值得注意：Trie 匹配到某个单词后，不能直接把整个 Trie 删掉，因为一个节点可能被多个前缀共享。比如"oath"和"oats"都经过"oat"，搜到"oath"后，'t'节点还有's'子节点可以用。后面我会具体讲怎么处理“匹配完成之后避免重复收集”的问题。

2. Trie 的 C 语言实现细节

2.1 节点结构设计：C 语言没有 Map，就用数组

很多高级语言实现 Trie 喜欢用Map<Character, Node>，但 C 语言没有现成的哈希表，最常规的做法是直接用数组。题目说明了网格中只包含小写英文字母，所以子节点数组长度固定为 26，下标对应'a'到'z'。

下面是节点定义：

typedef struct TrieNode { struct TrieNode* next[26]; int isEnd; // 标记该节点是否为某个单词的结尾 char* word; // 如果是结尾，记录完整的单词字符串 } TrieNode;

这里是 C 语言里非常经典的表达，每个节点自身包含 26 个指针，不存在的子节点是NULL。插入字符串时，如果某个字符对应的指针为空，就创建一个新节点并挂上来。

为什么要在节点里存char* word而不是存一个 bool 标志就够了？因为 DFS 在网格中递归时，递归栈只保存了坐标，并不知道完整路径上的字符是什么。如果只标记isEnd，到匹配终点时还要回溯拼接路径字符串。直接在isEnd节点上存一份完整单词的指针，收集结果时直接取出来用，省掉很多麻烦。

2.2 初始化与插入操作的几个细节

创建节点时建议用calloc而不是malloc。calloc会自动把所有字节清零，这样 26 个指针默认都是NULL，isEnd默认是 0，不用手动 memset。如果你用malloc，一定要记得memset(node, 0, sizeof(TrieNode))，不然后面判断next[idx] == NULL会出问题。

TrieNode* createNode() { TrieNode* node = (TrieNode*)calloc(1, sizeof(TrieNode)); return node; } void insert(TrieNode* root, const char* word) { TrieNode* p = root; for (int i = 0; word[i] != '\0'; i++) { int idx = word[i] - 'a'; if (p->next[idx] == NULL) { p->next[idx] = createNode(); } p = p->next[idx]; } p->isEnd = 1; p->word = (char*)word; }

这里有一个和 C 语言内存生命周期相关的小点：LeetCode 传入的char** words在整个函数执行期间都是有效的，每个words[i]指向的字符串内容不会变，所以直接把word指针存进节点是安全的。不需要用strdup去复制一份，因为题目给的输入数组生命周期覆盖整个求解过程。

如果是在别的不受控的场景里，比如自己写工具、从文件读单词，建议主动复制一份字符串再存进 Trie，避免外部数据释放后指针悬空。这属于 C 语言内存管理的基础问题，刷题时容易忽略，但实际工程里非常重要。

2.3 递归释放 Trie：内存泄漏这个坑很隐蔽

LeetCode 的 C 语言代码不会因为内存泄漏直接判错，但如果你在本地跑很多组测试用例，或者用 Valgrind 检查，就会看到大量泄漏报告。我在刷题群里见过不少朋友卡在这个点上，明明逻辑对了却总觉得不踏实。正确释放方式如下：

void freeTrie(TrieNode* node) { if (node == NULL) { return; } for (int i = 0; i < 26; i++) { if (node->next[i] != NULL) { freeTrie(node->next[i]); } } free(node); }

因为 Trie 是一个多叉树结构，释放必须是后序遍历：先释放所有子树，再释放当前节点。如果先 free 了当前节点，再去访问子节点就是典型的野指针操作，程序直接崩溃。

有人会问：如果p->word指向的字符串是动态分配的，freeTrie 里要不要 free 它？在这个题目里不需要，因为word直接指向 LeetCode 传入的words[i]，不属于 Trie 节点分配的内存。但如果是自己用strdup复制的，就需要在释放节点前 free 掉word。记得区分所有权。

2.4 C 语言二维数组与指针的访问方式

这题 C 语言版的函数签名是这样的：

char** findWords(char** board, int boardSize, int* boardColSize, char** words, int wordsSize, int* returnSize);

board是char**，board[i]指向第 i 行的字符串，board[i][j]就是第 i 行第 j 列的字符。boardColSize[i]表示第 i 行的列数。这个题目保证了矩阵是规整的，所以纵坐标范围就是boardColSize[0]，但写代码时最好还是用boardColSize[x]，防止测试用例不规整时越界。

C 语言刷题时最容易犯的问题之一，就是二维数组传参后的边界写错。boardSize表示行数，boardColSize[x]表示第 x 行的列数，这两者缺一不可。我在本地调试 212 题时，就曾因为只拿了boardSize当列数用，结果 4 个方向扩展时直接数组越界，程序崩溃在奇奇怪怪的位置。

3. DFS + 回溯：核心搜索过程

3.1 方向数组与边界检查

网格 DFS 的常规套路是预定义一个方向数组：

int dirs[4][2] = { {-1, 0}, // 上 {1, 0}, // 下 {0, -1}, // 左 {0, 1} // 右 };

每次递归从当前坐标(x, y)出发，依次尝试 4 个方向，新坐标是nx = x + dirs[i][0]，ny = y + dirs[i][1]。越界检查一定要放在访问数组元素之前：

if (nx < 0 || nx >= boardSize || ny < 0 || ny >= boardColSize[nx]) { continue; }

边界检查的顺序不能乱。先判断行是否越界，再取boardColSize[nx]去判断列。如果你先写了ny >= boardColSize[nx]再判断nx，那nx可能已经是负数或超出范围，访问boardColSize[nx]本身就是越界行为。这种感觉就像是查字典时先翻到不存在的页码再去读内容，很危险。

3.2 标记已访问：原地修改 board 还是额外开 visited 数组

同一个格子在一个单词的构造过程中不能重复使用，所以必须做访问标记。C 语言实现有两种主流方案。

第一种是开一个bool visited[boardSize][boardColSize[0]]，访问前标记，回溯时还原。优点是逻辑直观，不会修改原数组。但是题目模板是char** board，二维数组的行数和列数编译期不确定，在 C 语言里分配起来略麻烦，要用指针数组动态创建。

第二种方案我更喜欢：直接修改board[x][y] = '#'，递归返回时再还原成原来的字符。因为#不是小写字母，而 Trie 的 node 指针只可能往'a'到'z'方向走，一旦读到'#'，就无法匹配任何子节点，天然起到“该格子已访问”的作用。代码写起来非常简洁：

char c = board[x][y]; board[x][y] = '#'; // 递归四个方向... board[x][y] = c;

注意一点：#这个标记只在本题可行，因为题目明确限制字符集是小写字母。如果字符集包含#，就得换一个不可能出现的特殊字符，或者老老实实用 visited 数组。

3.3 DFS 主逻辑：匹配、收集、剪枝三件事

整体 DFS 函数可以写成这样：

void dfs(TrieNode* node, char** board, int boardSize, int boardColSize[], int x, int y, char** ans, int* ansPos) { if (x < 0 || x >= boardSize || y < 0 || y >= boardColSize[x]) { return; } char c = board[x][y]; if (c == '#') { return; } int idx = c - 'a'; if (node->next[idx] == NULL) { return; // Trie 中没有这个前缀，剪枝 } node = node->next[idx]; if (node->isEnd) { ans[(*ansPos)++] = node->word; node->isEnd = 0; // 防止同一个单词重复收集 } board[x][y] = '#'; for (int i = 0; i < 4; i++) { int nx = x + dirs[i][0]; int ny = y + dirs[i][1]; dfs(node, board, boardSize, boardColSize, nx, ny, ans, ansPos); } board[x][y] = c; }

这个函数每次接收的参数里，node是“当前 Trie 节点”。在进入某个格子之前，node代表的是从起点到上一个格子的路径在 Trie 中对应的节点。判断当前字符c是否有对应子节点，如果没有，立即 return，这就是核心剪枝。

判断node->isEnd时，把node->word存入答案数组，然后立刻把isEnd置 0。这一步非常重要。比如words里只有"oath"，但搜索路径可能通过不同的 DFS 分支再次到达'h'节点，如果不置 0，同一个单词会被重复收集两次，答案里出现两份"oath"。

3.4 为什么“置 0”不会破坏后续匹配

这是一个很容易纠结的点。有人担心：isEnd置 0 之后，如果后面还有单词要以当前节点作为前缀继续匹配，会不会受影响？

答案是不会。isEnd只表示“从根节点到当前节点的路径是不是一个完整单词”。置 0 只是说“这个完整单词已经收集过了，不用再收集”，子节点next数组完全没动。比如"oath"的'h'节点isEnd置 0 后，如果网格里还能继续搜索"oaths"，走到'h'节点时，它的next['s']仍然存在，可以继续向下走。所以该剪枝的照样剪，该扩展的照样扩展，不影响。

这里我也补充一个经验：如果words本身存在重复单词，比如words = ["oath", "oath"]，建树时第二个"oath"的插入路径已经把isEnd置 1，收集时第一个"oath"会把isEnd置 0，第二个"oath"就不会重复输出了。这相当于顺带解决了输入重复的情况。

3.5 起点遍历：每个格子都要试

在findWords函数里，对 board 上每一个格子都调用一次dfs：

int* returnSize = 0; char** ans = (char**)malloc(sizeof(char*) * wordsSize); for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardColSize[i]; j++) { dfs(root, board, boardSize, boardColSize, i, j, ans, returnSize); } }

这样做的含义是：单词可能从网格中任意位置开始，而且方向任意。每个格子作为起点时，DFS 会自己决定往哪里扩展。可能有人会想先判断board[i][j]是否是某个单词的首字母再进入 DFS，其实没必要，因为 DFS 第一步就会做node->next[idx]判断，不是可能首字母的直接返回，性能上差别很小，代码反而更简洁。

还需要注意结果数组ans的大小。最多不可能超过wordsSize，因为每个单词在 Trie 里最多被收集一次。按wordsSize分配是安全的，不会越界。

4. 完整实现与复杂度分析

4.1 完整 C 语言代码

把前面的模块拼起来，就是一个可以直接运行的版本：

#include <stdlib.h> #include <string.h> typedef struct TrieNode { struct TrieNode* next[26]; int isEnd; char* word; } TrieNode; TrieNode* createNode() { return (TrieNode*)calloc(1, sizeof(TrieNode)); } void insert(TrieNode* root, const char* word) { TrieNode* p = root; for (int i = 0; word[i]; i++) { int idx = word[i] - 'a'; if (!p->next[idx]) { p->next[idx] = createNode(); } p = p->next[idx]; } p->isEnd = 1; p->word = (char*)word; } void freeTrie(TrieNode* node) { if (!node) return; for (int i = 0; i < 26; i++) { if (node->next[i]) { freeTrie(node->next[i]); } } free(node); } static const int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; void dfs(TrieNode* node, char** board, int boardSize, int* boardColSize, int x, int y, char** ans, int* ansPos) { if (x < 0 || x >= boardSize || y < 0 || y >= boardColSize[x]) { return; } char c = board[x][y]; if (c == '#') { return; } int idx = c - 'a'; if (!node->next[idx]) { return; } node = node->next[idx]; if (node->isEnd) { ans[(*ansPos)++] = node->word; node->isEnd = 0; } board[x][y] = '#'; for (int i = 0; i < 4; i++) { int nx = x + dirs[i][0]; int ny = y + dirs[i][1]; dfs(node, board, boardSize, boardColSize, nx, ny, ans, ansPos); } board[x][y] = c; } char** findWords(char** board, int boardSize, int* boardColSize, char** words, int wordsSize, int* returnSize) { *returnSize = 0; if (boardSize == 0 || wordsSize == 0) { return NULL; } TrieNode* root = createNode(); for (int i = 0; i < wordsSize; i++) { insert(root, words[i]); } char** ans = (char**)malloc(sizeof(char*) * wordsSize); for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardColSize[i]; j++) { dfs(root, board, boardSize, boardColSize, i, j, ans, returnSize); } } freeTrie(root); return ans; }

这段代码我本地用几组用例测过，包括单词列表为空、网格为空、单词互相是前缀关系、单词之间存在重复等边界情况，表现都符合预期。这里建议把所有可执行代码贴进 VS Code 里配上 C 语言环境跑一遍，再对照调试看递归过程，理解会深刻很多。

4.2 时间复杂度与空间复杂度

建 Trie 的时间复杂度是O(所有单词的字符总数)，也就是把words里每个字符串都扫一遍。空间上，Trie 节点数最多不超过所有单词字符总数（实际因为共享前缀会更少），所以建树空间也是O(总字符数)。

DFS 阶段的时间复杂度理论上最坏是O(M * N * 4^L)，其中M是行数，N是列数，L是最长单词长度。这个上界和暴力 DFS 一样，但实际运行中会因为 Trie 剪枝大幅缩减。最坏情况需要构造一个非常极端的测试用例，让网格中每个位置都能一直匹配下去，而且所有单词都能在网格中找到，这种情况在实践中几乎不会出现。LeetCode 上这题的通过率不低，说明常规测试用例下 Trie 剪枝效果非常明显。

空间复杂度除了 Trie 之外，递归栈的深度最多等于最长单词长度L，visited 标记直接改在 board 上，没有额外分配，所以总体空间是O(总字符数 + L)。结果数组按wordsSize分配，算O(wordsSize)，但在复杂度分析中可以并入总字符数描述。

4.3 暴力法与 Trie + DFS 的直观对比

从这个对比能看出来，Trie + DFS 的核心收益并不是改变了最坏复杂度，而是把“多个单词共享前缀”这部分冗余操作几乎清零。当单词列表里存在大量共享前缀时，性能提升是数量级的。

5. 常见问题与实战排查

5.1 空指针崩溃：Trie 子节点判空

初写这道题时，很多人会在dfs里直接写node = node->next[c - 'a'];然后继续，忘记判断node->next[idx]是否为NULL。如果当前位置的字符在 Trie 中不存在对应子树，就会对一个空指针进行node->isEnd访问，程序直接崩溃。

正确的顺序一定是先判断，再下钻。我在上面代码里用的是：

if (!node->next[idx]) { return; } node = node->next[idx];

这两步顺序绝对不能反。就像下楼梯之前先看看脚下有没有台阶，不能先踩下去再低头看。

5.2 重复收集单词：isEnd 置 0 不能省

刚才已经讲过来龙去脉。这里再强调一遍表现：假设网格里有两个不同路径都能组成"oath"，DFS 第一次到达'h'节点时收集了"oath"，如果没有把isEnd置 0，第二次到达'h'节点时会把同一个单词再次写入结果数组。LeetCode 对答案顺序和重复性都有要求，多了重复项会导致 Wrong Answer。

如果测试用例里words本身就包含重复单词，处理方式也是一样的。两个相同单词插入 Trie，第二次只是在已有路径上走一遍，isEnd本来已经是 1；DFS 收集一次后置 0，就不会重复输出。所以不管重复来自网格的多条路径，还是来自输入列表本身，一行node->isEnd = 0;全解决。

5.3 坐标越界：列数不能直接用 boardColSize[0]

有些测试用例并不是规整矩形，虽然题目描述说是m x n的矩形网格，但 LeetCode 的boardColSize参数是按行给的，严谨起见每一行都要用自己的列数判断。如果盲目假设boardColSize[0]对每一行都有效，遇到boardColSize[i]不同或测试用例比较刁钻的情况就可能越界。

正确写法是把boardColSize[x]当成当前行的列数。这也是 C 语言中二维数组传参后必须依赖int* boardColSize的原因，char** board本身并不知道每一行有多长。

5.4 递归爆栈：一般不会，但可以主动避免

这题递归深度等于最长匹配路径的长度，正常情况下L不会超过几十。题目限制最长单词长度一般不夸张，所以递归爆栈风险很低。但 C 语言在调试模式下栈空间较小，如果你本地用超大网格测试，可以在心里有个预期。

如果想进一步优化，可以做一个小判断：如果某个 Trie 节点已经没有isEnd且没有任何子节点，那这个节点实际上已经“死了”，可以跳过。不过这个优化在本题收益有限，我一般不加，因为维护成本高，而且容易引入新的 bug。

5.5 本地环境与开发调试建议

我在 VS Code 里配好了 C 语言环境后用这一题做过完整调试。个人经验是，如果递归逻辑出错，直接在dfs函数入口打印当前坐标和当前字符，再配合打印 Trie 节点地址，很快就能定位问题。

另一个经验是：不要一次性写完所有代码再调试，先把 Trie 的 insert 写完，单独测试一棵树能不能正确建出来，遍历打印每个节点的isEnd和word；再写 DFS 逻辑。分层测试在 C 语言项目里特别重要，因为指针问题一旦混合在一起，排查成本会指数级上升。

6. 这题带来的延伸价值

单词搜索 II 本身是一道算法题，但它的解题模式在真实场景中非常常见。Trie 的“多模式匹配”思想被用在输入法自动补全、拼写检查、关键词过滤、搜索引擎的敏感词匹配等方向。C 语言实现 Trie 的经验直接可以迁移到这些工程实践里：动态内存分配、递归下降、节点复用、释放顺序，这些都是嵌入式或服务端 C 开发中高频出现的基础功。

我在实际写代码时的体会是，这题最值钱的部分不是“会背 TLE 解法”，而是理解“为什么 Trie 能把多个独立搜索合并成一次共享前缀搜索”。想通这一点之后，再看很多字符串匹配问题都会有一种豁然开朗的感觉。

最后再分享一个小技巧：想快速验证这个解法和暴力法的性能差异，自己构造一个单词列表，让里面 50 个单词共享同一个长度为 8 的前缀，网格设成 10x10，两个版本跑起来的速度差别大到肉眼可见。这也是我调试时最常用的性能对比手段，比空想复杂度直观得多。