企业官网建设流程全解析

LeetCode-Go 题解精讲：211. Design Add and Search Words Data Structure——基于 Trie 的通配符模糊搜索实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇文章围绕 LeetCode-Go 仓库中 211. Design Add and Search Words Data Structure 的题解文档 展开，深入剖析这道经典「字典树 + 通配符匹配」题目：如何设计一个支持addWord(word)与search(word)两种操作的数据结构，并让search支持用.匹配任意单个字母。读完本文，你将掌握 WordDictionary 的完整 Go 实现、递归模糊匹配的原理、与标准前缀树（LeetCode 208）的差异，以及如何用仓库中的测试用例验证正确性。

题目回顾

原题描述

设计一个支持以下两种操作的数据结构：

void addWord(word) bool search(word)

其中search(word)可以搜索一个字面单词，也可以搜索一个正则表达式字符串。表达式字符串只包含小写字母a-z或.，其中.可以代表任意一个字母。

题目给出的示例：

addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true

约束条件：所有单词均由小写字母a-z组成。

题目大意

简单来说，本题要求实现一个名为WordDictionary的数据结构，具备两个核心能力：

1. 精确插入：addWord(word)把单词存入结构；
2. 模糊查找：search(word)不仅支持完整单词的精确匹配，还支持包含.的模式匹配——只要模式串与某个已插入单词在长度和字母位置上逐一对应即可命中。

这与搜索引擎中的「前缀提示 + 通配符补全」、IDE 中的模糊匹配、拼写纠错等场景在思路上高度一致，是经典前缀树应用的一个自然延伸。

解题思路：在经典 Trie 上叠加模糊查找

原文档明确指出，这一题是LeetCode 208 题的加强版：在第 208 题经典的 Trie（前缀树）基础上，增加了模糊查找（.通配符）的功能，其余实现一模一样。

为什么选择前缀树

• 插入与精确查找的时间复杂度都与单词长度线性相关，不依赖词典规模；
• 天然共享前缀，空间利用率高；
• 树形结构便于在匹配到.时枚举该节点的所有子分支进行「递归回溯」。

仓库中配套的基础实现位于 208. Implement Trie (Prefix Tree) 的题解源码.go)，其Trie结构与 211 题的WordDictionary几乎同构，可以作为对照阅读：

type Trie struct { isWord bool children map[rune]*Trie }

可以看到，208 题的Insert、Search与 211 题的AddWord、Search在节点定义、插入逻辑上高度一致，唯一的本质区别是 211 题在Search中增加了对.的递归分支枚举。因此，理解 208 题是实现本题的捷径。

模糊查找的本质

普通的 Trie 查找是「沿着确定的字符路径一路向下」；而一旦出现.，当前字符不再指向唯一子节点，查找就变成了一次多分支选择：必须逐个尝试当前节点的每一个子节点，只要任何一个分支能匹配完剩余部分，整个模式就算匹配成功。这正是本题递归实现的由来。

仓库源码逐行解析

完整的实现位于 211. Design Add and Search Words Data Structure.go，下面是完整源码：

package leetcode type WordDictionary struct { children map[rune]*WordDictionary isWord bool } /** Initialize your data structure here. */ func Constructor211() WordDictionary { return WordDictionary{children: make(map[rune]*WordDictionary)} } /** Adds a word into the data structure. */ func (this *WordDictionary) AddWord(word string) { parent := this for _, ch := range word { if child, ok := parent.children[ch]; ok { parent = child } else { newChild := &WordDictionary{children: make(map[rune]*WordDictionary)} parent.children[ch] = newChild parent = newChild } } parent.isWord = true } /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */ func (this *WordDictionary) Search(word string) bool { parent := this for i, ch := range word { if rune(ch) == '.' { isMatched := false for _, v := range parent.children { if v.Search(word[i+1:]) { isMatched = true } } return isMatched } else if _, ok := parent.children[rune(ch)]; !ok { return false } parent = parent.children[rune(ch)] } return len(parent.children) == 0 || parent.isWord }

数据结构定义

type WordDictionary struct { children map[rune]*WordDictionary isWord bool }

• children：以rune为键的子节点映射表，用于存放从当前节点出发的各字符分支；
• isWord：布尔标记，表示从根节点走到当前节点的这条路径是否构成一个完整单词（例如插入bad与badminton时，bad节点既是前缀节点又需要标记为单词结尾）。

构造函数

func Constructor211() WordDictionary { return WordDictionary{children: make(map[rune]*WordDictionary)} }

初始化一个空的WordDictionary，仅分配子节点映射表，isWord保持零值false。返回的是值类型而非指针，后续通过方法接收者this *WordDictionary以指针方式修改内部结构。

AddWord：标准前缀树插入

func (this *WordDictionary) AddWord(word string) { parent := this for _, ch := range word { if child, ok := parent.children[ch]; ok { parent = child } else { newChild := &WordDictionary{children: make(map[rune]*WordDictionary)} parent.children[ch] = newChild parent = newChild } } parent.isWord = true }

插入逻辑与 208 题Trie.Insert完全一致：

1. 从根节点出发，逐字符遍历单词；
2. 若当前字符对应的子节点已存在，直接沿该分支下移；
3. 若不存在，则新建节点并挂到当前节点的children映射中；
4. 单词遍历结束后，把最后一个节点标记为isWord = true。

由于题目保证单词均为小写a-z，for range按 rune 遍历与按 byte 遍历在这里结果相同，使用map[rune]*WordDictionary也天然兼容后续可能的 Unicode 扩展。

Search：带通配符的递归匹配

func (this *WordDictionary) Search(word string) bool { parent := this for i, ch := range word { if rune(ch) == '.' { isMatched := false for _, v := range parent.children { if v.Search(word[i+1:]) { isMatched = true } } return isMatched } else if _, ok := parent.children[rune(ch)]; !ok { return false } parent = parent.children[rune(ch)] } return len(parent.children) == 0 || parent.isWord }

Search是整个实现的灵魂，可拆解为三个分支：

1. 遇到.：枚举所有子节点并递归回溯

当ch等于.时，说明当前这一位可以是任意字母。实现不再沿单一路径下移，而是遍历parent.children中的每一个子节点，对每个子节点递归调用v.Search(word[i+1:])，即「匹配剩余模式串」。只要任一分支返回true，整体即为匹配成功。

这是本题相对 208 题的核心新增逻辑：普通 Trie 的Search只能逐字符精确比对，而这里通过递归实现了通配符的多分支搜索，代价是匹配.时需要遍历当前节点的所有分支。

2. 遇到普通字母：沿唯一分支下移

若子节点不存在，立即返回false（剪枝）；存在则下移继续匹配。

3. 模式串遍历结束：判断是否构成完整单词

return len(parent.children) == 0 || parent.isWord

当模式串的所有字符都匹配完毕后，能否算作命中，取决于最终节点是否为单词结尾（isWord）。从实现上看，len(parent.children) == 0是一个附加的兜底条件：由于AddWord创建的每个单词终点都会设置isWord = true，在常规插入流程下该条件不会改变判定结果，可以理解为代码在「叶子节点」这一特殊情况上的冗余保险。

复杂度分析（可由代码结构推断）

• AddWord：时间复杂度 O(L)，L 为单词长度，每步仅做一次 map 查找或插入；空间上每个字符对应一个节点。
• Search（无.）：时间复杂度 O(L)，与精确查找一致，沿途若缺字符立即剪枝返回。
• Search（含.）：最坏情况下（如模式串全部为.）需要对树的每一层枚举全部分支，复杂度会退化到与整棵前缀树的节点规模相关。这也是模糊搜索相对精确搜索的主要代价。
• 空间复杂度：与插入的所有单词的字符总数成正比，且前缀共享可显著压缩存储。

测试用例验证

仓库为本题提供了配套测试，位于 211. Design Add and Search Words Data Structure_test.go：

func Test_Problem211(t *testing.T) { obj := Constructor211() obj.AddWord("bad") obj.AddWord("dad") obj.AddWord("mad") obj.AddWord("bat") param1 := obj.Search("pad") // 期望 false param2 := obj.Search("bad") // 期望 true param3 := obj.Search(".ad") // 期望 true param4 := obj.Search("b..") // 期望 true }

该测试完整复现了题目官方示例，并额外插入了"bat"以验证「同前缀多分支」场景（b下同时存在bad与bat）：

• search("pad")：p分支不存在，返回false；
• search("bad")：精确匹配，bad节点isWord = true，返回true；
• search(".ad")：首字符为.，枚举b/d/m三个分支，b分支匹配"ad"成功，返回true；
• search("b..")：b分支确定后，剩余两个.逐层枚举，bad/bat均可命中，返回true。

运行该测试即可验证实现正确性，测试文件同时展示了Constructor211、AddWord、Search的完整调用方式，与源码文件尾部的用法注释相互印证：

// obj := Constructor(); // obj.AddWord(word); // param_2 := obj.Search(word);

与 208 题 Trie 的对比小结

从源码结构看，211 题复用了 208 题的节点组织方式，仅在查找算法上增加了递归分支枚举，因此把 208 题的实现作为模板、再叠加通配符处理，是解决本题最直接、最经典的路径。

扩展思考：模糊匹配的应用场景

虽然本题是算法题，但WordDictionary的「Trie + 通配符递归」思想在真实工程中有广泛对应：

• 输入法 / 搜索框提示：用 Trie 存储词库，用.模拟「任意字符」完成模糊补全；
• 拼写纠错与容错匹配：允许用户输入中的个别字符错误，通过通配符放宽匹配条件；
• 字典类游戏的单词判定（如填字游戏）：用模式串在词库中检索所有符合形态的候选词。

在这类场景中，若通配符占比很高，可考虑引入缓存、剪枝或改用其他索引结构来缓解递归枚举的开销——这些优化方向正是从本题解法自然延伸出来的工程问题。

总结

LeetCode 211 题的本质是「前缀树 + 递归模糊匹配」：以 208 题的标准 Trie 为基础，在Search中遇到.时枚举当前节点的所有子分支并递归匹配剩余模式串。LeetCode-Go 仓库中的实现（题解源码 与 测试用例）代码简洁、逻辑清晰，覆盖了题目的全部示例，是学习前缀树进阶应用的优质范本。若想进一步夯实基础，可先阅读 208 题的标准 Trie 实现.go)，再回到本题体会「精确匹配 → 通配匹配」的演进路径。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go