AI 写 Trie 树，第一版直接崩了——搜索提示到底怎么实现的？
读完本文你将了解前缀树的原理 | AI 从暴力到最优的解题过程 | 搜索框自动补全背后的结构 | 面试中 Trie 怎么考 题目原题实现一个 Trie前缀树包含 insert、search 和 startsWith 三种操作。项目说明输入Trie trie new Trie(); trie.insert(“apple”); trie.search(“apple”) → true输出trie.search(“app”) → false; trie.startsWith(“app”) → true约束1 ≤ word.length ≤ 2000仅包含小写英文字母最多调用 3×10⁴ 次 先问一个问题打开百度输入深度学还没打完下拉框就弹出深度学习“深度神经网络”“深度求索”——怎么做到的别跟我说用 HashMap。存 1000 万个词条按前缀搜HashMap 得扫全表。你以为的最优解数据量一上来就废了。 第一版AI 的朴素解法用 HashSet 硬搜AI 第一次写这题想都不想就上了 HashSetclassTrie:def__init__(self):self.wordsset()definsert(self,word:str)-None:self.words.add(word)defsearch(self,word:str)-bool:returnwordinself.wordsdefstartsWith(self,prefix:str)-bool:forwinself.words:ifw.startswith(prefix):returnTruereturnFalse原因很简单存起来→查一下是人类最自然的直觉。不是笨是没意识到前缀搜索的量级问题。复杂度分析insert: O(1)空间 O(N×L)search: O(1)空间 O(1)startsWith:O(N×L)— 每次前缀查询遍历全部 N 个单词问题在于insert 和 search 很快但 startsWith 每次扫全表。存 100 万个词用户每敲一个字母遍历 100 万次——手机直接发烫。 AI 的自我优化被点醒后AI 开始一步步改第 1 次优化给前缀建索引classTrie:def__init__(self):self.wordsset()self.prefix_setset()definsert(self,word:str)-None:self.words.add(word)foriinrange(1,len(word)1):self.prefix_set.add(word[:i])defstartsWith(self,prefix:str)-bool:returnprefixinself.prefix_set把所有前缀也存进去startsWith 变成 O(1)。但 insert 空间炸了——“apple” 要存 “a”, “ap”, “app”, “appl”, “apple”。第 2 次优化Trie 树才是正解classTrieNode:def__init__(self):self.children{}self.is_endFalseclassTrie:def__init__(self):self.rootTrieNode()definsert(self,word:str)-None:nodeself.rootforchinword:ifchnotinnode.children:node.children[ch]TrieNode()nodenode.children[ch]node.is_endTruedefsearch(self,word:str)-bool:nodeself._find_node(word)returnnodeisnotNoneandnode.is_enddefstartsWith(self,prefix:str)-bool:returnself._find_node(prefix)isnotNonedef_find_node(self,prefix:str):nodeself.rootforchinprefix:ifchnotinnode.children:returnNonenodenode.children[ch]returnnodeRootabpple*re*ad*复杂度分析insert: 时间 O(L)空间 O(L) — 每个字符一个节点search: 时间 O(L)空间 O(1)startsWith: 时间 O(L)空间 O(1)这才是真正的 Trie前缀共享存储查询只走一条路径跟数据量无关。☕ Java 实现classTrieNode{TrieNode[]childrennewTrieNode[26];booleanisEnd;}classTrie{privateTrieNoderoot;publicTrie(){rootnewTrieNode();}publicvoidinsert(Stringword){TrieNodenoderoot;for(charch:word.toCharArray()){intidxch-a;if(node.children[idx]null){node.children[idx]newTrieNode();}nodenode.children[idx];}node.isEndtrue;}publicbooleansearch(Stringword){TrieNodenodefindNode(word);returnnode!nullnode.isEnd;}publicbooleanstartsWith(Stringprefix){returnfindNode(prefix)!null;}privateTrieNodefindNode(Stringprefix){TrieNodenoderoot;for(charch:prefix.toCharArray()){intidxch-a;if(node.children[idx]null)returnnull;nodenode.children[idx];}returnnode;}}Java 版用TrieNode[26]代替 HashMap——利用仅含小写字母这个约束数组索引比哈希查找快一个数量级。 算法模式拆解这题属于Trie前缀树模式20 种核心算法模式里最像造数据结构的一个。怎么识别前缀匹配— 按前缀搜索、自动补全、词典匹配空间共享— 多个字符串共享前缀省空间快速查找— O(L) 完成操作跟数据量无关模式变体变体描述经典题标准 Trie基础插入搜索前缀查询LeetCode 208通配符 Trie支持.匹配任意字符LeetCode 211单词搜索 Trie在矩阵中搜索单词LeetCode 212文件系统 Trie以路径为键的前缀树LeetCode 588Trie 模式标准 TrieLeetCode 208通配符搜索LeetCode 211单词搜索 IILeetCode 212文件系统LeetCode 588️ 真实产品场景百度搜索框的自动补全背后就是一棵巨大的 Trie 树用户输入深度学 → 从 Trie 根节点沿s-h-e-n-d-u-x-u-e走到对应节点以该节点为起点做 DFS收集所有以深度学习开头的热门搜索词结合热度排序返回 Top 5Roots*henduxue*suo*suoIDE 代码提示也是 Trie输入System.ou→ 编辑器沿着 Trie 走到对应节点 → 返回System.out.println()等候选。手机输入法的拼音输入更是 Trie 的经典应用——拼音到汉字的映射本质上就是一颗巨大的 Trie 树。✅ 面试官的点评级别评分标准关键点通过写出标准 Trie 实现insert/search/startsWith 正确了解 O(L) 复杂度良好 通配符搜索能扩展到 LeetCode 211 的.匹配优秀 自动补全 剪枝能设计searchSuggestions()加 Top K 排序加分项主动问字符集多大——小写用数组Unicode 用 HashMap讨论空间优化isEnd换成int count记录经过的单词数提到 Trie 的短板空间大可以用 Ternary Search Tree 或 Radix Tree 替代踩坑点❌ 用 Map 没问题但面试官更想看数组❌ 忘了处理空输入❌ startsWith 和 search 搞混——前者不检查 isEnd 同类题推荐题目一句话思路LeetCode 211— 添加与搜索单词在 Trie 搜索中支持.通配符用 DFS 回溯LeetCode 212— 单词搜索 II矩阵 TrieDFS 剪枝比纯回溯快 10 倍LeetCode 588— 设计内存文件系统Trie 的变体路径名作为 key文件/目录作为 value来源说明✅ 已验证LeetCode 208 官方题解 AI 实测 文档/论文算法教材《算法导论》Trie 章节
