你在搜索框里敲下“算法”两个字下拉列表立刻冒出“算法导论”“算法面试题”“算法工程师薪资”——这种“输入即提示”的能力背后几乎一定是Trie前缀树读作try。哈希表也能查词为什么自动补全非它不可哈希表只会回答“这个词在不在”而Trie天然回答另外两个问题“以这个前缀开头的词有哪些”“按字典序下一个是什么”。前缀检索是Trie的主场哈希表在这里只能全表扫描。今天用LC.208把Trie从零实现一遍再用LC.211的通配符搜索逼出一个反直觉的结论Trie的查询一旦遇到.就变成了回溯——你会看到“做选择 → 递归 → 撤销”这套熟悉的模板。 题目速览 30秒读懂实现Trie类insert(word)插入字符串search(word)判断word是否在树中startsWith(prefix)判断是否有单词以prefix开头示例insert(apple) search(apple) → true search(app) → false ← 注意 startsWith(app) → true ← 注意 insert(app) search(app) → true约束词长 ≤ 2000仅小写字母。关键对比search(app)是false而startsWith(app)是true——“app这条路走得通”不等于“app是一个完整单词”。这一个区别就是Trie最经典的丢分点。 核心思路用公共前缀换空间换来前缀检索的O(L)暴力为什么不行哈希表存所有单词search是O(1)startsWith只能遍历整张表逐个比对前缀——O(n×L)。词表上万时输入每个字符都要扫一遍全表自动补全的“即时”体验就没了。换个角度所有以app开头的单词应该共享a→p→p这条路径(root) | a | p | p / \ l (end) | e | (end)那么“查前缀”就退化成“从根沿边走 L 步”——复杂度只与查询词长度有关与词表规模彻底无关。节点需要什么children指向下一层字符的边isEnd标记“到这儿为止是一个完整单词”没有isEnd就无法区分app和apple——这正是示例里search(app)为false的原因。三个操作各自做什么操作做什么一句话insert逐字符走边不存在就建走完打isEnd建路search逐字符走中途断掉返回false走完还要看isEnd走路 验终点startsWith逐字符走只看能否走通不看isEnd只走路口诀searchstartsWith 检查isEnd。️ 图解算法手把手走一遍以依次插入apple、app为例★表示isEnd True步骤操作树的结构变化说明1insert(apple)root→a→p→p→l→e★新建6个节点末端打标2insert(app)root→a→p→p★→l→e★a/p/p三条边已存在直接复用只在第3个p上打标插入apple后再插入app没有新建任何节点——这就是“公共前缀换空间”的直观体现。再走一遍三个查询查询行走路径能否走通终点isEnd结果search(apple)a→p→p→l→e✅Truetruesearch(app)a→p→p✅FalsefalsestartsWith(app)a→p→p✅不检查truesearch(b)b❌ 根下无b—false 代码实现Python JavaLC.208实现Trie前缀树Python哈希表版字符集开放classTrieNode:def__init__(self):self.children{}# 字符 - 子节点self.is_endFalse# 是否为单词结尾classTrie:def__init__(self):self.rootTrieNode()definsert(self,word:str)-None:nodeself.rootforchinword:ifchnotinnode.children:# 复用已有前缀node.children[ch]TrieNode()nodenode.children[ch]node.is_endTrue# 关键终点必须打标defsearch(self,word:str)-bool:nodeself._walk(word)returnnodeisnotNoneandnode.is_enddefstartsWith(self,prefix:str)-bool:returnself._walk(prefix)isnotNonedef_walk(self,s:str):nodeself.rootforchins:ifchnotinnode.children:returnNonenodenode.children[ch]returnnodeJava数组版固定26个小写字母classTrie{privatestaticclassNode{Node[]childrennewNode[26];// 数组比HashMap更快booleanisEnd;}privatefinalNoderootnewNode();publicvoidinsert(Stringword){Nodecurroot;for(charc:word.toCharArray()){intic-a;if(cur.children[i]null)cur.children[i]newNode();curcur.children[i];}cur.isEndtrue;// 终点打标区分app与apple}publicbooleansearch(Stringword){Nodenodewalk(word);returnnode!nullnode.isEnd;}publicbooleanstartsWith(Stringprefix){returnwalk(prefix)!null;// 只走不验}privateNodewalk(Strings){Nodecurroot;for(charc:s.toCharArray()){intic-a;if(cur.children[i]null)returnnull;curcur.children[i];}returncur;}}⚠️防坑提醒search必须检查is_endstartsWith不检查——这是最高频的错误。Java用c - a做下标别写错成c。字符集不固定时用HashMap别硬编码26。 延伸LC.211通配符搜索Trie 回溯LC.211要求.可匹配任意字符。走到的节点若有多个分支可选就必须每个都试——于是查询退化成DFSclassWordDictionary:def__init__(self):self.root{}defaddWord(self,word:str)-None:nodeself.rootforchinword:nodenode.setdefault(ch,{})node[#]True# #作为结束标记defsearch(self,word:str)-bool:defdfs(i,node):ifilen(word):return#innode chword[i]ifch.:# 通配符所有分支都试returnany(dfs(i1,nxt)fork,nxtinnode.items()ifk!#)ifchnotinnode:returnFalsereturndfs(i1,node[ch])returndfs(0,self.root)这就是回溯骨架for横向枚举分支 递归纵向深入 命中即返回。 进阶一删除单词面试爱问LeetCode 208不考删除但面试爱问。难点不在“删标记”而在“删完之后要不要回收节点”deferase(self,word:str)-None:path[]nodeself.rootforchinword:ifchnotinnode.children:returnpath.append((node,ch))nodenode.children[ch]ifnotnode.is_end:returnnode.is_endFalse# ① 先摘标记# ② 自底向上回收没孩子、不是终点 → 只服务于被删的词whilepathandnotnode.childrenandnotnode.is_end:parent,chpath.pop()delparent.children[ch]nodeparent两个易错点① 必须先判断is_end再摘标记② 回收条件要同时检查children和is_end中间节点可能是别的单词终点。 进阶二按前缀取全部单词自动补全核心defwords_with_prefix(self,prefix:str)-list[str]:nodeself._walk(prefix)ifnodeisNone:return[]out[]defdfs(cur,path):ifcur.is_end:out.append(path)forchinsorted(cur.children):# 排序 → 天然字典序dfs(cur.children[ch],pathch)dfs(node,prefix)returnout这就是输入法候选词的完整形态。想加“热度排序”只要在is_end旁边再挂一个freq字段——Trie的节点是可扩展的这正是它比哈希表强的地方。⏱️ 复杂度分析面试必问操作时间复杂度说明insertO(L)逐字符走L步searchO(L)同上末尾多一次isEnd判断startsWithO(L)同上search含.最坏O(26^L)每个.都可能分叉26路关键三个操作的复杂度都不含n。这是它对哈希表前缀查询O(n·L)的决定性优势。空间O(总字符数)——有公共前缀时远小于此。实测O(L)与O(n·L)差多少10万单词、1000次前缀查询做法复杂度实测耗时相对Trie走树O(L)0.0003s1×列表全表扫描O(n·L)1.558s5682× 慢set全表扫描O(n·L)4.328s15784× 慢差距三个数量级。空间侧实测10万单词总字符648,397Trie节点358,464——公共前缀省下44.7%节点。⚠️纠正一个常见误解“哈希表O(1)比Trie O(L) 快”只在整词查询上成立。一旦问“以x开头的有哪些”哈希表退化为全表扫描O(1)优势当场消失。 举一反三5道高频变体题题号题目与本题的关系LC.211添加与搜索单词.通配符 → 回溯LC.677键值映射Trie节点挂数值支持前缀求和LC.720词典中最长的单词Trie DFS判定“每个前缀都在词典里”LC.421数组中两数的最大异或值Trie用在二进制上LC.212单词搜索IITrie 网格回溯 面试追问模拟提前准备惊艳全场Q1Trie和哈希表到底怎么选三个判据① 需要前缀查询自动补全、前缀统计→ Trie② 需要按字典序遍历所有key → Trie③ 只判“在不在”且追求实现简单 → 哈希表更省事。另外Trie在大量公共前缀的数据上比哈希表省空间。Q2children用数组还是 HashMap字符集固定且小26个小写字母→ 数组O(1)且无哈希开销字符集大Unicode或稀疏 → HashMap省空间。工程上还有双数组Trie中文分词里常见。Q3Trie的缺点是什么能优化吗指针开销大、缓存不友好。优化方向压缩Trie / Radix Tree把单分支链合并、数组化存储用下标代替指针。 实战小技巧刷题党必备口诀insert建路search走路 验终点startsWith只走路。模板TrieNode children isEnd三个操作 walk 不同收尾。防坑search必须检查is_end.通配符退化成回溯。 实际应用场景不止是刷题搜索框自动补全 / 输入法候选词Trie最经典的落地敏感词过滤命中isEnd即拦截进阶是AC自动机路由表最长前缀匹配IP前缀查表拼写检查 / 模糊匹配Trie 编辑距离剪枝 今日思考题LC.211的通配符搜索最坏是O(26^L)如果词表里单词长度普遍是20这个复杂度还能接受吗提示可以按长度分组或用正则引擎的思路。