C语言实现 Trie + DFS 解决 LeetCode 212 单词搜索 II

项目标题: 212. 单词搜索 IIWord 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一个单词长度是L10每次从起点出发最坏情况下每个位置有 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 喜欢用MapCharacter, 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 个指针默认都是NULLisEnd默认是 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 上每一个格子都调用一次dfsint* 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 之外递归栈的深度最多等于最长单词长度Lvisited 标记直接改在 board 上没有额外分配所以总体空间是O(总字符数 L)。结果数组按wordsSize分配算O(wordsSize)但在复杂度分析中可以并入总字符数描述。4.3 暴力法与 Trie DFS 的直观对比对比项暴力法每个单词独立 DFSTrie DFS时间复杂度O(k * M * N * 4^L)建树O(totalLen)搜索最坏O(M * N * 4^L)实际远低于此空间复杂度visited 数组复用较低Trie 占用额外空间但属于一次性成本冗余搜索公共前缀被重复扫描公共前缀只走一遍代码复杂度低容易实现中高需要 Trie 结构但值得从这个对比能看出来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 不能省刚才已经讲过来龙去脉。这里再强调一遍表现假设网格里有两个不同路径都能组成oathDFS 第一次到达h节点时收集了oath如果没有把isEnd置 0第二次到达h节点时会把同一个单词再次写入结果数组。LeetCode 对答案顺序和重复性都有要求多了重复项会导致 Wrong Answer。如果测试用例里words本身就包含重复单词处理方式也是一样的。两个相同单词插入 Trie第二次只是在已有路径上走一遍isEnd本来已经是 1DFS 收集一次后置 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两个版本跑起来的速度差别大到肉眼可见。这也是我调试时最常用的性能对比手段比空想复杂度直观得多。