 —— 一份可复用的 Go 语言前缀树模板)
LeetCode-Go 题解精讲208. Implement Trie (Prefix Tree) —— 一份可复用的 Go 语言前缀树模板【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go前缀树Trie是字符串处理类题目中的高频核心数据结构。本文以 LeetCode 208 题「Implement Trie (Prefix Tree)」为载体结合 LeetCode-Go 仓库中 leetcode/0208.Implement-Trie-Prefix-Tree 的完整实现与测试用例逐行剖析insert、search、startsWith三个核心操作的底层原理并展示这套实现如何作为通用 Trie 模板被仓库其他题目直接复用。读完本文你既能透彻理解前缀树的 Go 实现细节也能掌握一套可直接迁移到词频统计、自动补全、敏感词过滤等场景的代码骨架。题目背景与核心要求LeetCode 208 题要求设计一个支持以下三种操作的前缀树Trie又称字典树Insert(word)向树中插入一个单词Search(word)判断某个单词是否完整存在于树中StartsWith(prefix)判断树中是否存在以给定前缀开头的任意单词。题目给出的操作示例来自 网站题解文档Trie trie new Trie(); trie.insert(apple); trie.search(apple); // returns true trie.search(app); // returns false trie.startsWith(app); // returns true trie.insert(app); trie.search(app); // returns true这里最值得注意的语义差异是search(app)在未插入 app 之前返回false而startsWith(app)返回true。这说明search 要求「完整单词」而startsWith 只要求「前缀可达」两者的唯一区别在于对终点节点isWord标记的判断这正是本题实现的关键细节。题目附带两条输入约束实现时可据此简化边界处理所有输入仅包含小写字母a-z所有输入均为非空字符串。前缀树的核心思想以空间换前缀共享在深入代码之前先建立直观模型。Trie 的本质是一棵多叉树但与二叉搜索树不同它的边edge携带字符从根节点到任意节点的路径拼接起来就是一个字符串前缀。多个单词共享相同前缀时这些前缀路径在树中只存储一次。以插入 apple 和 app 为例共享的 app 路径只有一份root | a | p | p ── (isWordtrue表示 app 完整存在) | l | e ── (isWordtrue表示 apple 完整存在)正是这种「公共前缀只存一次」的路径复用使得 Trie 在前缀查询、最长公共前缀、词频统计等场景中拥有远高于朴素遍历的查找效率——每次查询只需沿字符路径走O(L)步L为字符串长度与字典中已存单词的总数无关。数据结构设计map 驱动的子节点存储仓库中的实现位于 208. Implement Trie (Prefix Tree).go核心结构只有两个字段type Trie struct { isWord bool children map[rune]*Trie }isWord bool标记从根节点到当前节点的路径是否构成一个完整单词。这是Search与StartsWith产生语义差异的关键开关children map[rune]*Trie以字符为键、子节点为值的哈希表负责承载「边上的字符」。与教科书常见的「定长 26 元素数组[26]*Trie」方案相比map[rune]*Trie有两个明显优势天然支持 Unicodemap[rune]的键类型是 Go 的 rune即 int32配合代码中for _, ch : range word的按 rune 遍历这套实现无需任何改动即可处理中文等多字节字符而固定数组方案受限于 ASCII 字母表按需分配内存每个节点只为其实际存在的子字符分配 map 桶避免了 26 元素数组带来的固定空间开销。代价是 map 的哈希查找比数组索引略慢、常数更大但在 LeetCode 的题目约束小写字母a-z下性能完全足够且代码更通用、可读性更好。构造函数同样简洁为每个新建节点初始化空 map并显式将isWord置为falsefunc Constructor208() Trie { return Trie{isWord: false, children: make(map[rune]*Trie)} }插入操作 Insert沿路径下沉缺失即新建func (this *Trie) Insert(word string) { parent : this for _, ch : range word { if child, ok : parent.children[ch]; ok { parent child } else { newChild : Trie{children: make(map[rune]*Trie)} parent.children[ch] newChild parent newChild } } parent.isWord true }插入的算法流程可以拆解为三步游标初始化从根节点this开始用局部变量parent记录当前所在节点逐字符下沉对单词的每个字符ch先在parent.children中查找是否已有对应子节点——已存在则直接沿该子节点继续走共享前缀路径不存在则新建一个Trie节点挂到parent.children[ch]上再继续下沉终点打标记整条路径走完后将最终节点即单词最后一个字符对应的节点的isWord置为true。最后一个步骤是 Insert 的灵魂没有parent.isWord true就无法区分「路径恰好经过某字符」与「单词完整存在」两种状态。例如插入 apple 后路径上 a、ap、app、appl 节点都真实存在但它们都不是完整单词只有isWordtrue的 apple 终点才算数。查询操作 Search路径可达之外还需 isWord 为真func (this *Trie) Search(word string) bool { parent : this for _, ch : range word { if child, ok : parent.children[ch]; ok { parent child continue } return false } return parent.isWord }Search 分两段完成路径检查沿单词字符逐层下沉若任何一步在children中找不到对应子节点说明该单词前缀路径尚未被任何已插入单词覆盖直接返回false终点检查路径全部走通后返回终点节点的isWord值。这解释了开头的示例——插入 apple 后执行search(app)路径 a→p→p 全部可达但终点节点isWord仍为false因为 app 从未作为完整单词插入于是返回false而在insert(app)之后同一查询返回true。前缀查询 StartsWith只查路径不问终点func (this *Trie) StartsWith(prefix string) bool { parent : this for _, ch : range prefix { if child, ok : parent.children[ch]; ok { parent child continue } return false } return true }StartsWith 与 Search 的代码几乎逐行相同唯一区别是最后一行直接返回true不再检查isWord。因为「存在以某前缀开头的单词」只要求前缀路径被覆盖过并不要求前缀本身是完整单词。例如插入 apple 后startsWith(app)返回true尽管 app 并非完整单词——只要路径 a→p→p 存在后续就必然挂着至少一个完整单词。三个方法共用的游标式循环结构恰好构成一份易读、易记的 Trie 模板骨架。复杂度分析设插入/查询的字符串长度为L字典中已插入单词总数为N指标复杂度说明Insert 时间复杂度O(L)每个字符一次 map 查找或插入与 N 无关Search 时间复杂度O(L)每个字符一次 map 查找StartsWith 时间复杂度O(L)每个字符一次 map 查找空间复杂度O(所有单词字符总数)每个字符路径对应一个节点公共前缀仅存一份与传统哈希表对比哈希表做前缀查询需要遍历全部单词做前缀匹配O(N·L)而 Trie 天然支持 O(L) 的前缀检索这是它在自动补全、拼写检查、IP 路由等场景胜出的根本原因。测试验证覆盖通过与否的完整路径仓库为本题配套了单元测试 208. Implement Trie (Prefix Tree)_test.go用go test即可运行。测试用例严格对照题目示例并额外覆盖了两类负例param5 : obj.Search(banana) if param5 { t.Fatalf(Search(\banana\) %v, want false, param5) } param6 : obj.StartsWith(ban) if param6 { t.Fatalf(StartsWith(\ban\) %v, want false, param6) }Search(banana)验证「从未插入的单词」返回false路径在首字符b处即断裂StartsWith(ban)验证「不存在的前缀」返回false。加上前面对 apple / app 的搜索、前缀查询与插入后再查询的组合测试形成了「正向命中 路径缺失 isWord 区分」的完整覆盖与仓库 README 声称的 100% test coverage 目标一致。模板级复用同一个 Trie 撑起多道题目题目文档 明确指出「本题的实现可以作为 Trie 的模板」仓库源码验证了这一说法——Trie结构与Constructor208被其他题目直接复用648. Replace Words替换单词解法二replaceWords1直接调用trie : Constructor208()将字典中的词根批量Insert再对句子中每个单词从短到长做trie.Search(value[:i])找到最短词根即替换。整棵前缀树零修改直接嵌入业务逻辑211. Design Add and Search Words Data Structure添加与搜索单词其WordDictionary结构与本题Trie如出一辙children map[rune]*WordDictionaryisWord boolAddWord的插入逻辑几乎逐行复刻本题Insert仅因支持通配符.而在Search中加入了递归回溯分支。这从侧面印证了本题实现作为「标准 Trie 模板」的辐射能力。从源码结构看仓库的通用数据结构库 structures如ListNode、TreeNode、Stack、Queue等同样遵循「单题实现 跨题复用」的组织哲学先在某一道典型题中沉淀出干净的基础实现再被其他题目引用或改造。小结一份值得收藏的 Trie 模板回顾整个实现核心只有四个要点节点自指children map[rune]*Trie让每个节点都能作为下一层子树的根天然递归isWord 开关区分「前缀可达」与「完整单词」是Search/StartsWith语义差异的全部来源统一游标循环三个方法共享「沿字符路径下沉缺失即返回」的骨架仅终点判断不同map 存储子节点兼顾 Unicode 支持与按需分配比定长数组更通用。当你在面试或工程中需要实现自动补全、词频统计、最长公共前缀、敏感词过滤或 IP 路由匹配时这份来自 LeetCode-Go 的 Trie 实现可以直接作为起点——它已经在 208 题的测试中验证过正确性并在 648、211 等题目中证明了自己的可扩展性。【免费下载链接】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 题解精讲：208. Implement Trie (Prefix Tree) —— 一份可复用的 Go 语言前缀树模板
LeetCode-Go 题解精讲208. Implement Trie (Prefix Tree) —— 一份可复用的 Go 语言前缀树模板【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go前缀树Trie是字符串处理类题目中的高频核心数据结构。本文以 LeetCode 208 题「Implement Trie (Prefix Tree)」为载体结合 LeetCode-Go 仓库中 leetcode/0208.Implement-Trie-Prefix-Tree 的完整实现与测试用例逐行剖析insert、search、startsWith三个核心操作的底层原理并展示这套实现如何作为通用 Trie 模板被仓库其他题目直接复用。读完本文你既能透彻理解前缀树的 Go 实现细节也能掌握一套可直接迁移到词频统计、自动补全、敏感词过滤等场景的代码骨架。题目背景与核心要求LeetCode 208 题要求设计一个支持以下三种操作的前缀树Trie又称字典树Insert(word)向树中插入一个单词Search(word)判断某个单词是否完整存在于树中StartsWith(prefix)判断树中是否存在以给定前缀开头的任意单词。题目给出的操作示例来自 网站题解文档Trie trie new Trie(); trie.insert(apple); trie.search(apple); // returns true trie.search(app); // returns false trie.startsWith(app); // returns true trie.insert(app); trie.search(app); // returns true这里最值得注意的语义差异是search(app)在未插入 app 之前返回false而startsWith(app)返回true。这说明search 要求「完整单词」而startsWith 只要求「前缀可达」两者的唯一区别在于对终点节点isWord标记的判断这正是本题实现的关键细节。题目附带两条输入约束实现时可据此简化边界处理所有输入仅包含小写字母a-z所有输入均为非空字符串。前缀树的核心思想以空间换前缀共享在深入代码之前先建立直观模型。Trie 的本质是一棵多叉树但与二叉搜索树不同它的边edge携带字符从根节点到任意节点的路径拼接起来就是一个字符串前缀。多个单词共享相同前缀时这些前缀路径在树中只存储一次。以插入 apple 和 app 为例共享的 app 路径只有一份root | a | p | p ── (isWordtrue表示 app 完整存在) | l | e ── (isWordtrue表示 apple 完整存在)正是这种「公共前缀只存一次」的路径复用使得 Trie 在前缀查询、最长公共前缀、词频统计等场景中拥有远高于朴素遍历的查找效率——每次查询只需沿字符路径走O(L)步L为字符串长度与字典中已存单词的总数无关。数据结构设计map 驱动的子节点存储仓库中的实现位于 208. Implement Trie (Prefix Tree).go核心结构只有两个字段type Trie struct { isWord bool children map[rune]*Trie }isWord bool标记从根节点到当前节点的路径是否构成一个完整单词。这是Search与StartsWith产生语义差异的关键开关children map[rune]*Trie以字符为键、子节点为值的哈希表负责承载「边上的字符」。与教科书常见的「定长 26 元素数组[26]*Trie」方案相比map[rune]*Trie有两个明显优势天然支持 Unicodemap[rune]的键类型是 Go 的 rune即 int32配合代码中for _, ch : range word的按 rune 遍历这套实现无需任何改动即可处理中文等多字节字符而固定数组方案受限于 ASCII 字母表按需分配内存每个节点只为其实际存在的子字符分配 map 桶避免了 26 元素数组带来的固定空间开销。代价是 map 的哈希查找比数组索引略慢、常数更大但在 LeetCode 的题目约束小写字母a-z下性能完全足够且代码更通用、可读性更好。构造函数同样简洁为每个新建节点初始化空 map并显式将isWord置为falsefunc Constructor208() Trie { return Trie{isWord: false, children: make(map[rune]*Trie)} }插入操作 Insert沿路径下沉缺失即新建func (this *Trie) Insert(word string) { parent : this for _, ch : range word { if child, ok : parent.children[ch]; ok { parent child } else { newChild : Trie{children: make(map[rune]*Trie)} parent.children[ch] newChild parent newChild } } parent.isWord true }插入的算法流程可以拆解为三步游标初始化从根节点this开始用局部变量parent记录当前所在节点逐字符下沉对单词的每个字符ch先在parent.children中查找是否已有对应子节点——已存在则直接沿该子节点继续走共享前缀路径不存在则新建一个Trie节点挂到parent.children[ch]上再继续下沉终点打标记整条路径走完后将最终节点即单词最后一个字符对应的节点的isWord置为true。最后一个步骤是 Insert 的灵魂没有parent.isWord true就无法区分「路径恰好经过某字符」与「单词完整存在」两种状态。例如插入 apple 后路径上 a、ap、app、appl 节点都真实存在但它们都不是完整单词只有isWordtrue的 apple 终点才算数。查询操作 Search路径可达之外还需 isWord 为真func (this *Trie) Search(word string) bool { parent : this for _, ch : range word { if child, ok : parent.children[ch]; ok { parent child continue } return false } return parent.isWord }Search 分两段完成路径检查沿单词字符逐层下沉若任何一步在children中找不到对应子节点说明该单词前缀路径尚未被任何已插入单词覆盖直接返回false终点检查路径全部走通后返回终点节点的isWord值。这解释了开头的示例——插入 apple 后执行search(app)路径 a→p→p 全部可达但终点节点isWord仍为false因为 app 从未作为完整单词插入于是返回false而在insert(app)之后同一查询返回true。前缀查询 StartsWith只查路径不问终点func (this *Trie) StartsWith(prefix string) bool { parent : this for _, ch : range prefix { if child, ok : parent.children[ch]; ok { parent child continue } return false } return true }StartsWith 与 Search 的代码几乎逐行相同唯一区别是最后一行直接返回true不再检查isWord。因为「存在以某前缀开头的单词」只要求前缀路径被覆盖过并不要求前缀本身是完整单词。例如插入 apple 后startsWith(app)返回true尽管 app 并非完整单词——只要路径 a→p→p 存在后续就必然挂着至少一个完整单词。三个方法共用的游标式循环结构恰好构成一份易读、易记的 Trie 模板骨架。复杂度分析设插入/查询的字符串长度为L字典中已插入单词总数为N指标复杂度说明Insert 时间复杂度O(L)每个字符一次 map 查找或插入与 N 无关Search 时间复杂度O(L)每个字符一次 map 查找StartsWith 时间复杂度O(L)每个字符一次 map 查找空间复杂度O(所有单词字符总数)每个字符路径对应一个节点公共前缀仅存一份与传统哈希表对比哈希表做前缀查询需要遍历全部单词做前缀匹配O(N·L)而 Trie 天然支持 O(L) 的前缀检索这是它在自动补全、拼写检查、IP 路由等场景胜出的根本原因。测试验证覆盖通过与否的完整路径仓库为本题配套了单元测试 208. Implement Trie (Prefix Tree)_test.go用go test即可运行。测试用例严格对照题目示例并额外覆盖了两类负例param5 : obj.Search(banana) if param5 { t.Fatalf(Search(\banana\) %v, want false, param5) } param6 : obj.StartsWith(ban) if param6 { t.Fatalf(StartsWith(\ban\) %v, want false, param6) }Search(banana)验证「从未插入的单词」返回false路径在首字符b处即断裂StartsWith(ban)验证「不存在的前缀」返回false。加上前面对 apple / app 的搜索、前缀查询与插入后再查询的组合测试形成了「正向命中 路径缺失 isWord 区分」的完整覆盖与仓库 README 声称的 100% test coverage 目标一致。模板级复用同一个 Trie 撑起多道题目题目文档 明确指出「本题的实现可以作为 Trie 的模板」仓库源码验证了这一说法——Trie结构与Constructor208被其他题目直接复用648. Replace Words替换单词解法二replaceWords1直接调用trie : Constructor208()将字典中的词根批量Insert再对句子中每个单词从短到长做trie.Search(value[:i])找到最短词根即替换。整棵前缀树零修改直接嵌入业务逻辑211. Design Add and Search Words Data Structure添加与搜索单词其WordDictionary结构与本题Trie如出一辙children map[rune]*WordDictionaryisWord boolAddWord的插入逻辑几乎逐行复刻本题Insert仅因支持通配符.而在Search中加入了递归回溯分支。这从侧面印证了本题实现作为「标准 Trie 模板」的辐射能力。从源码结构看仓库的通用数据结构库 structures如ListNode、TreeNode、Stack、Queue等同样遵循「单题实现 跨题复用」的组织哲学先在某一道典型题中沉淀出干净的基础实现再被其他题目引用或改造。小结一份值得收藏的 Trie 模板回顾整个实现核心只有四个要点节点自指children map[rune]*Trie让每个节点都能作为下一层子树的根天然递归isWord 开关区分「前缀可达」与「完整单词」是Search/StartsWith语义差异的全部来源统一游标循环三个方法共享「沿字符路径下沉缺失即返回」的骨架仅终点判断不同map 存储子节点兼顾 Unicode 支持与按需分配比定长数组更通用。当你在面试或工程中需要实现自动补全、词频统计、最长公共前缀、敏感词过滤或 IP 路由匹配时这份来自 LeetCode-Go 的 Trie 实现可以直接作为起点——它已经在 208 题的测试中验证过正确性并在 648、211 等题目中证明了自己的可扩展性。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考