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

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的数据结构具备两个核心能力精确插入addWord(word)把单词存入结构模糊查找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[i1:]) { 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完全一致从根节点出发逐字符遍历单词若当前字符对应的子节点已存在直接沿该分支下移若不存在则新建节点并挂到当前节点的children映射中单词遍历结束后把最后一个节点标记为isWord true。由于题目保证单词均为小写a-zfor 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[i1:]) { 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[i1:])即「匹配剩余模式串」。只要任一分支返回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.gofunc 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与batsearch(pad)p分支不存在返回falsesearch(bad)精确匹配bad节点isWord true返回truesearch(.ad)首字符为.枚举b/d/m三个分支b分支匹配ad成功返回truesearch(b..)b分支确定后剩余两个.逐层枚举bad/bat均可命中返回true。运行该测试即可验证实现正确性测试文件同时展示了Constructor211、AddWord、Search的完整调用方式与源码文件尾部的用法注释相互印证// obj : Constructor(); // obj.AddWord(word); // param_2 : obj.Search(word);与 208 题 Trie 的对比小结维度208. Implement Trie211. WordDictionary核心数据结构Triechildren isWordWordDictionarychildren isWord插入方法Insert(word)AddWord(word)查找方法Search(word)精确匹配Search(word)支持.通配前缀查询提供StartsWith(prefix)不涉及查找实现逐字符沿单一路径下移遇.枚举全部分支递归回溯从源码结构看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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考