LeetCode-Go 题解211. Design Add and Search Words Data StructureTrie 通配符模糊搜索【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 211 题「Design Add and Search Words Data Structure」展开讲解如何基于字典树Trie设计一个同时支持精确插入与通配符模糊查询的数据结构WordDictionary。文章以仓库 关联题解文档 为主线并结合 仓库核心实现 与 单元测试 逐行剖析实现细节。读完本文你将掌握Trie 的基本结构与插入流程、.通配符的递归回溯搜索实现、前缀树在模糊匹配场景下的边界处理以及如何在当前仓库中运行测试验证结论。一、题目要求需要什么样的数据结构题目要求设计一个支持以下两种操作的数据结构void addWord(word) bool search(word)其中search(word)可以搜索一个普通单词也可以搜索一个只包含字母a-z或.的正则表达式风格的字符串.可以代表任意一个字母。同时题目给出约束可以假设所有单词都由小写字母a-z组成。示例addWord(bad) addWord(dad) addWord(mad) search(pad) - false search(bad) - true search(.ad) - true search(b..) - true从示例可以看出关键点search(.ad)能命中bad、dad、mad中任意一个即返回truesearch(b..)需要匹配以b开头、总长度为 3 的已插入单词。这一题的核心诉求是插入操作需要支持后续的高效前缀查询而搜索操作又必须支持任意位置的通配符匹配。这正是前缀树Trie的典型应用场景。二、解题思路经典 Trie 的加强版原题解文档给出了非常明确的思路定位见 题解文档设计一个WordDictionary数据结构要求具有addWord(word)和search(word)两个操作并且支持模糊查找本题是第 208 题Implement Trie / Prefix Tree的加强版在第 208 题经典 Trie 的基础上增加模糊查找功能其余实现完全相同。也就是说本题的解法建立在标准 Trie 之上核心差异只有一处——Search方法遇到.时需要遍历当前节点的所有子节点做递归搜索。仓库中两个题解的实现可以互相对照第 208 题标准 Trie 实现.go)包含Insert、Search、StartsWith三个方法是标准的无通配符前缀树第 211 题实现仅保留AddWord与Search并在Search中加入.通配符的递归回溯。三、完整代码实现原题解文档给出了完整的 Go 实现仓库源码 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 } /** * Your WordDictionary object will be instantiated and called as such: * obj : Constructor(); * obj.AddWord(word); * param_2 : obj.Search(word); */四、源码级剖析每一处设计如何工作4.1 节点结构children与isWordtype WordDictionary struct { children map[rune]*WordDictionary isWord bool }每个 Trie 节点用map[rune]*WordDictionary保存子节点key是边上的字符value是指向下一个节点的指针isWord标记从根到当前节点的路径是否构成一个完整单词。选用rune作为 key 意味着对 Unicode 字符同样有天然的兼容性——虽然题目约束只有a-z但该结构并不限制字符集。这与第 208 题的Trie结构见 208 题实现.go) 中的children map[rune]*Trie完全一致。4.2AddWord标准的字典树插入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 }插入过程逐字符沿 Trie 下行从根节点this开始令parent指向当前节点对单词中的每个字符ch若parent.children[ch]已存在则直接沿该边下行否则创建新节点并挂到parent.children[ch]上处理完最后一个字符后将parent.isWord置为true标记该路径为一个完整单词。需要注意AddWord走的是共享前缀路径。例如依次插入bad、dad、mad三个单词共享根节点各自拥有独立的首字符分支而插入bat时ba前缀会与已有的bad共享。4.3Search的精确匹配部分} else if _, ok : parent.children[rune(ch)]; !ok { return false } parent parent.children[rune(ch)]当字符不是.时逻辑与标准 Trie 的查找一致若当前节点不存在对应子节点则直接返回false否则沿子节点下行。这也是为何本题被称为 208 题的加强版——没有.时Search退化成一个普通的前缀树查找。4.4Search的通配符部分递归回溯if rune(ch) . { isMatched : false for _, v : range parent.children { if v.Search(word[i1:]) { isMatched true } } return isMatched }这是本题与第 208 题唯一的本质差异。遇到.时当前位置可以是当前节点任意一个子节点因此需要枚举当前节点所有的子节点并对每个子节点递归调用Search处理剩余后缀word[i1:]是.之后的剩余部分只要任意一个分支返回true整个搜索即为成功isMatched true若当前节点没有任何子节点parent.children为空循环体不会执行直接返回false这与字典树中不存在该长度的单词这一事实一致。这里需要特别指出实现细节代码中isMatched true后没有提前break而是继续遍历完所有子节点。从正确性看结果不变但这一点说明该实现更侧重于结构简洁遍历过程中所有分支都会被递归执行。读者在理解时可以把它看作标准的「存在性回溯」命中即成功。4.5 收尾判定len(parent.children) 0 || parent.isWordreturn len(parent.children) 0 || parent.isWord当搜索串的所有字符都匹配完成后需要判定「匹配是否成功」。标准 Trie 此时只看isWord但本实现额外加上了len(parent.children) 0这个条件。结合递归调用场景可以理解这样写的用意若当前节点isWord true说明存在一个完整单词与搜索串完全一致返回true若当前节点不是单词结尾但没有任何子节点说明它是 Trie 的叶子节点。在.通配符递归搜索中可能出现「剩余后缀为空、当前停在某个叶子节点」的路径此时该路径上没有更深的字符可走len(parent.children) 0使得这种情况也能返回true。需要说明的是这一判定是仓库实现中的保守写法对于题目约束单词均由a-z组成而言isWord true的分支已经覆盖了所有合法命中场景len(parent.children) 0分支更多是为了在递归回溯边界上保持行为的一致性。理解这一点有助于看清递归调用链上的终止条件。五、与第 208 题标准 Trie 的对照能力第 208 题Trie源码.go)第 211 题WordDictionary源码数据结构children map[rune]*TrieisWordchildren map[rune]*WordDictionaryisWord插入Insert(word)逐字符建链AddWord(word)逐字符建链逻辑相同精确查找Search(word)逐字符下行看isWord无.时逐字符下行逻辑相同前缀查询StartsWith(prefix)不需要通配符查询不支持遇到.递归枚举所有子节点从源码结构看两个数据结构在节点定义与插入逻辑上几乎一一对应第 211 题正是在第 208 题 Trie 的骨架上「加挂」了.通配符的递归搜索这与原题解文档中「在第 208 题经典的 Trie 上加上了模糊查找的功能」的表述完全吻合。六、复杂度分析基于实现推导以下结论基于上述实现从算法结构推导得出时间复杂度AddWord(word)单次遍历每个字符做一次 map 查找或插入为 O(L)其中 L 为单词长度Search(word)不含.时同样为 O(L)含.时每个.都可能触发对所有子节点的递归最坏情况下例如树的分支因子接近字母表大小、搜索串为.....这类全通配串会近似遍历整棵 Trie为 O(26^L) 量级这也是 Trie 做模糊匹配固有的代价。空间复杂度所有已插入单词共享前缀存储空间取决于 Trie 中实际节点总数至多不超过「所有单词字符数之和」级别。仓库并未在文档中声明具体的性能测试数据以上为对实现本身的算法性推导不构成实测基准。七、单元测试与运行验证仓库为本题提供了完整的单元测试 211. Design Add and Search Words Data Structure_test.go测试流程如下Constructor211()创建空的字典树依次AddWord(bad)、AddWord(dad)、AddWord(mad)、AddWord(bat)依次断言Search(pad)→falsepa前缀不存在Search(bad)→true精确命中Search(.ad)→true通配首字母命中bad/dad/madSearch(b..)→true通配后两个字符命中bad/bat。其中bat是题目示例之外的额外插入项用于验证b..的搜索仍然成立。测试中还打印了每一步的obj状态便于在go test -v下观察插入与查询过程中字典树的形态变化。在仓库根目录下可以通过 gotest.sh 脚本运行全部题解测试该脚本对./leetcode/...下所有包执行带覆盖率收集的测试go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以只针对本题目录单独验证go test -v ./leetcode/0211.Design-Add-and-Search-Words-Data-Structure/go test会把_test.go与同目录源码放在同一个测试包内编译执行因此可以直接验证上述四个搜索断言。八、总结本题是第 208 题的加强版数据结构、插入逻辑与精确查找全部沿用经典 Trie唯一的新增点是在Search中处理.通配符——枚举当前节点所有子节点并递归匹配剩余后缀实现采用map[rune]*WordDictionary作为子节点存储天然支持任意字符且插入与精确查找均为 O(L) 复杂度仓库的单元测试覆盖了题目示例的全部四种查询场景可用 gotest.sh 一键运行验证。掌握 Trie 上的通配符递归回溯是解决自动补全、拼写检查、正则前缀匹配等真实场景问题的基础能力本题即是最具代表性的入门练习之一。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解：211. Design Add and Search Words Data Structure（Trie + 通配符模糊搜索）
LeetCode-Go 题解211. Design Add and Search Words Data StructureTrie 通配符模糊搜索【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 211 题「Design Add and Search Words Data Structure」展开讲解如何基于字典树Trie设计一个同时支持精确插入与通配符模糊查询的数据结构WordDictionary。文章以仓库 关联题解文档 为主线并结合 仓库核心实现 与 单元测试 逐行剖析实现细节。读完本文你将掌握Trie 的基本结构与插入流程、.通配符的递归回溯搜索实现、前缀树在模糊匹配场景下的边界处理以及如何在当前仓库中运行测试验证结论。一、题目要求需要什么样的数据结构题目要求设计一个支持以下两种操作的数据结构void addWord(word) bool search(word)其中search(word)可以搜索一个普通单词也可以搜索一个只包含字母a-z或.的正则表达式风格的字符串.可以代表任意一个字母。同时题目给出约束可以假设所有单词都由小写字母a-z组成。示例addWord(bad) addWord(dad) addWord(mad) search(pad) - false search(bad) - true search(.ad) - true search(b..) - true从示例可以看出关键点search(.ad)能命中bad、dad、mad中任意一个即返回truesearch(b..)需要匹配以b开头、总长度为 3 的已插入单词。这一题的核心诉求是插入操作需要支持后续的高效前缀查询而搜索操作又必须支持任意位置的通配符匹配。这正是前缀树Trie的典型应用场景。二、解题思路经典 Trie 的加强版原题解文档给出了非常明确的思路定位见 题解文档设计一个WordDictionary数据结构要求具有addWord(word)和search(word)两个操作并且支持模糊查找本题是第 208 题Implement Trie / Prefix Tree的加强版在第 208 题经典 Trie 的基础上增加模糊查找功能其余实现完全相同。也就是说本题的解法建立在标准 Trie 之上核心差异只有一处——Search方法遇到.时需要遍历当前节点的所有子节点做递归搜索。仓库中两个题解的实现可以互相对照第 208 题标准 Trie 实现.go)包含Insert、Search、StartsWith三个方法是标准的无通配符前缀树第 211 题实现仅保留AddWord与Search并在Search中加入.通配符的递归回溯。三、完整代码实现原题解文档给出了完整的 Go 实现仓库源码 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 } /** * Your WordDictionary object will be instantiated and called as such: * obj : Constructor(); * obj.AddWord(word); * param_2 : obj.Search(word); */四、源码级剖析每一处设计如何工作4.1 节点结构children与isWordtype WordDictionary struct { children map[rune]*WordDictionary isWord bool }每个 Trie 节点用map[rune]*WordDictionary保存子节点key是边上的字符value是指向下一个节点的指针isWord标记从根到当前节点的路径是否构成一个完整单词。选用rune作为 key 意味着对 Unicode 字符同样有天然的兼容性——虽然题目约束只有a-z但该结构并不限制字符集。这与第 208 题的Trie结构见 208 题实现.go) 中的children map[rune]*Trie完全一致。4.2AddWord标准的字典树插入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 }插入过程逐字符沿 Trie 下行从根节点this开始令parent指向当前节点对单词中的每个字符ch若parent.children[ch]已存在则直接沿该边下行否则创建新节点并挂到parent.children[ch]上处理完最后一个字符后将parent.isWord置为true标记该路径为一个完整单词。需要注意AddWord走的是共享前缀路径。例如依次插入bad、dad、mad三个单词共享根节点各自拥有独立的首字符分支而插入bat时ba前缀会与已有的bad共享。4.3Search的精确匹配部分} else if _, ok : parent.children[rune(ch)]; !ok { return false } parent parent.children[rune(ch)]当字符不是.时逻辑与标准 Trie 的查找一致若当前节点不存在对应子节点则直接返回false否则沿子节点下行。这也是为何本题被称为 208 题的加强版——没有.时Search退化成一个普通的前缀树查找。4.4Search的通配符部分递归回溯if rune(ch) . { isMatched : false for _, v : range parent.children { if v.Search(word[i1:]) { isMatched true } } return isMatched }这是本题与第 208 题唯一的本质差异。遇到.时当前位置可以是当前节点任意一个子节点因此需要枚举当前节点所有的子节点并对每个子节点递归调用Search处理剩余后缀word[i1:]是.之后的剩余部分只要任意一个分支返回true整个搜索即为成功isMatched true若当前节点没有任何子节点parent.children为空循环体不会执行直接返回false这与字典树中不存在该长度的单词这一事实一致。这里需要特别指出实现细节代码中isMatched true后没有提前break而是继续遍历完所有子节点。从正确性看结果不变但这一点说明该实现更侧重于结构简洁遍历过程中所有分支都会被递归执行。读者在理解时可以把它看作标准的「存在性回溯」命中即成功。4.5 收尾判定len(parent.children) 0 || parent.isWordreturn len(parent.children) 0 || parent.isWord当搜索串的所有字符都匹配完成后需要判定「匹配是否成功」。标准 Trie 此时只看isWord但本实现额外加上了len(parent.children) 0这个条件。结合递归调用场景可以理解这样写的用意若当前节点isWord true说明存在一个完整单词与搜索串完全一致返回true若当前节点不是单词结尾但没有任何子节点说明它是 Trie 的叶子节点。在.通配符递归搜索中可能出现「剩余后缀为空、当前停在某个叶子节点」的路径此时该路径上没有更深的字符可走len(parent.children) 0使得这种情况也能返回true。需要说明的是这一判定是仓库实现中的保守写法对于题目约束单词均由a-z组成而言isWord true的分支已经覆盖了所有合法命中场景len(parent.children) 0分支更多是为了在递归回溯边界上保持行为的一致性。理解这一点有助于看清递归调用链上的终止条件。五、与第 208 题标准 Trie 的对照能力第 208 题Trie源码.go)第 211 题WordDictionary源码数据结构children map[rune]*TrieisWordchildren map[rune]*WordDictionaryisWord插入Insert(word)逐字符建链AddWord(word)逐字符建链逻辑相同精确查找Search(word)逐字符下行看isWord无.时逐字符下行逻辑相同前缀查询StartsWith(prefix)不需要通配符查询不支持遇到.递归枚举所有子节点从源码结构看两个数据结构在节点定义与插入逻辑上几乎一一对应第 211 题正是在第 208 题 Trie 的骨架上「加挂」了.通配符的递归搜索这与原题解文档中「在第 208 题经典的 Trie 上加上了模糊查找的功能」的表述完全吻合。六、复杂度分析基于实现推导以下结论基于上述实现从算法结构推导得出时间复杂度AddWord(word)单次遍历每个字符做一次 map 查找或插入为 O(L)其中 L 为单词长度Search(word)不含.时同样为 O(L)含.时每个.都可能触发对所有子节点的递归最坏情况下例如树的分支因子接近字母表大小、搜索串为.....这类全通配串会近似遍历整棵 Trie为 O(26^L) 量级这也是 Trie 做模糊匹配固有的代价。空间复杂度所有已插入单词共享前缀存储空间取决于 Trie 中实际节点总数至多不超过「所有单词字符数之和」级别。仓库并未在文档中声明具体的性能测试数据以上为对实现本身的算法性推导不构成实测基准。七、单元测试与运行验证仓库为本题提供了完整的单元测试 211. Design Add and Search Words Data Structure_test.go测试流程如下Constructor211()创建空的字典树依次AddWord(bad)、AddWord(dad)、AddWord(mad)、AddWord(bat)依次断言Search(pad)→falsepa前缀不存在Search(bad)→true精确命中Search(.ad)→true通配首字母命中bad/dad/madSearch(b..)→true通配后两个字符命中bad/bat。其中bat是题目示例之外的额外插入项用于验证b..的搜索仍然成立。测试中还打印了每一步的obj状态便于在go test -v下观察插入与查询过程中字典树的形态变化。在仓库根目录下可以通过 gotest.sh 脚本运行全部题解测试该脚本对./leetcode/...下所有包执行带覆盖率收集的测试go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以只针对本题目录单独验证go test -v ./leetcode/0211.Design-Add-and-Search-Words-Data-Structure/go test会把_test.go与同目录源码放在同一个测试包内编译执行因此可以直接验证上述四个搜索断言。八、总结本题是第 208 题的加强版数据结构、插入逻辑与精确查找全部沿用经典 Trie唯一的新增点是在Search中处理.通配符——枚举当前节点所有子节点并递归匹配剩余后缀实现采用map[rune]*WordDictionary作为子节点存储天然支持任意字符且插入与精确查找均为 O(L) 复杂度仓库的单元测试覆盖了题目示例的全部四种查询场景可用 gotest.sh 一键运行验证。掌握 Trie 上的通配符递归回溯是解决自动补全、拼写检查、正则前缀匹配等真实场景问题的基础能力本题即是最具代表性的入门练习之一。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考