LeetCode 前缀树（Trie）专题：原理剖析、三语言模板与实战题解

文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载本篇文章以 thinkings/trie.md 为核心骨架系统讲解字典树Trie又称前缀树的数据结构原理、插入与查询操作、Java / Python / JavaScript 三语言实现模板与复杂度分析并结合当前 leetcode 仓库中的 208. 实现 Trie、211. 添加与搜索单词、212. 单词搜索 II、472. 连接词、820. 单词的压缩编码、1032. 字符流 等真题题解说明哪些场景该用前缀树、模板如何变形适配不同题目这一实战难点。读完本文你将掌握前缀树的完整原理、可直接封装复用的标准模板以及六道经典题目的解题套路与剪枝技巧。简介为什么需要前缀树使用百度搜索时输入一语搜索栏会给出一语道破一语成谶读 chen等推荐文本这属于模糊匹配给定一个模糊的 query返回相关推荐列表。很明显HashMap 并不容易做到模糊匹配而 Trie 可以实现基于前缀的模糊搜索。注意这里的模糊搜索也仅仅是基于前缀的。例如上面的例子搜索道破就不会匹配到一语道破而只能匹配道破 xx。Trie 本身就是一个树型结构即一颗多叉树。它的核心操作是插入和查找删除操作很少使用。前缀树字典树在 LeetCode 的 Trie 标签下共有 17 道题目其中 2 道简单、8 道中等、7 道困难是面试中非常经典的数据结构专题。基本概念假想一个场景给你若干单词 words 和一系列关键字 keywords让你判断 keywords 是否在 words 中存在或者判断 keywords 中的单词是否有 words 中的单词的前缀。比如pre就是pres的前缀之一。朴素的想法是遍历 keywords对于 keywords 中的每一项都遍历 words 列表判断二者是否相等或是否为其前缀。这种算法的时间复杂度是 $O(m \times n)$其中 m 为 words 的平均长度n 为 keywords 的平均长度。我们可以将 words 存储到一棵树上这棵树叫做前缀树。每一个节点存储一个字符外加一个控制信息表示是否是单词结尾实际使用过程可能会有细微差别不过变化不大。节点根结点无实际意义每一个节点数据域存储一个字符每个节点中的控制域可以自定义如isWord是否是单词、count该前缀出现的次数等需根据实际问题分析需要什么。一个可能的前缀树节点结构Javaprivate class TrieNode { int count; //表示以该处节点构成的串的个数 int preCount; //表示以该处节点构成的前缀的字串的个数 TrieNode[] children; TrieNode() { children new TrieNode[26]; count 0; preCount 0; } }可以看出 TrieNode 是一个递归的数据结构其结构类似多叉树只是多了几个属性记录额外信息罢了。比如count可以用来判断以当前节点结束的单词个数preCount可以用来判断以当前节点结束的前缀个数。举个例子前缀树中存了两个单词lu和lucifer那么单词lu有一个lu前缀有两个。前缀树结构大概如下l(count 0, preCount2) u(count 1, preCount2) c(count 0, preCount1) i(count 0, preCount1) f(count 0, preCount1) e(count 0, preCount1) f(count 1, preCount1)Trie 的插入构建 Trie 的核心就是插入指的就是将单词words全部依次插入到前缀树中。假定给出几个单词 words [she, he, her, good, god]构造出的 Trie 中从根结点出发到某一粉色节点即单词结尾节点所经过的字符组成的单词在单词列表中出现过。当然我们也可以给树的每个节点加个 count 属性代表根结点到该节点所构成的字符串前缀出现的次数。树的构造非常简单插入新单词的时候就从根结点出发一个字符一个字符插入有对应的字符节点就更新对应的属性没有就创建一个Trie 的查询查询更简单给定一个 Trie 和一个单词和插入的过程类似一个字符一个字符查找若中途有个字符没有对应节点 → Trie 不含该单词若字符串遍历完了都有对应节点但最后一个字符对应的节点并不是单词结尾不是粉色节点→ Trie 不含该单词。Trie 模板了解了 Trie 的使用场景以及基本的 API最后就是用代码来实现了。这里提供 Java、Python、JavaScript 三种语言的代码核心 API 均为三个insert(word)插入单词、search(word)精确查找单词、startsWith(prefix)前缀查询。Java Codeclass Trie { TrieNode root; public Trie() { root new TrieNode(); } public void insert(String word) { TrieNode node root; for (int i 0; i word.length(); i) { if (node.children[word.charAt(i) - a] null) node.children[word.charAt(i) - a] new TrieNode(); node node.children[word.charAt(i) - a]; node.preCount; } node.count; } public boolean search(String word) { TrieNode node root; for (int i 0; i word.length(); i) { if (node.children[word.charAt(i) - a] null) return false; node node.children[word.charAt(i) - a]; } return node.count 0; } public boolean startsWith(String prefix) { TrieNode node root; for (int i 0; i prefix.length(); i) { if (node.children[prefix.charAt(i) - a] null) return false; node node.children[prefix.charAt(i) - a]; } return node.preCount 0; } private class TrieNode { int count; //表示以该处节点构成的串的个数 int preCount; //表示以该处节点构成的前缀的字串的个数 TrieNode[] children; TrieNode() { children new TrieNode[26]; count 0; preCount 0; } } }Python Codeclass TrieNode: def __init__(self): self.count 0 # 表示以该处节点构成的串的个数 self.preCount 0 # 表示以该处节点构成的前缀的字串的个数 self.children {} class Trie: def __init__(self): self.root TrieNode() def insert(self, word): node self.root for ch in word: if ch not in node.children: node.children[ch] TrieNode() node node.children[ch] node.preCount 1 node.count 1 def search(self, word): node self.root for ch in word: if ch not in node.children: return False node node.children[ch] return node.count 0 def startsWith(self, prefix): node self.root for ch in prefix: if ch not in node.children: return False node node.children[ch] return node.preCount 0JavaScript Codevar Trie function() { this.children {}; this.count 0 //表示以该处节点构成的串的个数 this.preCount 0 // 表示以该处节点构成的前缀的字串的个数 }; Trie.prototype.insert function(word) { let node this.children; for(let char of word){ if(!node[char]) node[char] {} node node[char] node.preCount 1 } node.count 1 }; Trie.prototype.search function(word) { let node this.children; for(let char of word){ if(!node[char]) return false node node[char] } return node.count 0 }; Trie.prototype.startsWith function(prefix) { let node this.children; for(let char of prefix){ if(!node[char]) return false node node[char] } return node.preCount 0 };复杂度分析插入和查询的时间复杂度是 $O(len(key))$key 是待插入查找的字串建树的最坏空间复杂度是 $O(m^{n})$m 是字符集中字符个数n 是字符串长度。回答开头的问题回到开头的问题给你若干单词 words 和一系列关键字 keywords判断 keywords 是否在 words 中存在或者判断 keywords 中的单词是否有 words 中的单词的前缀。如果使用 Trie 来解首先需要建立 Trie这部分的时间复杂度是 $O(t)$其中 t 为 words 的总字符数这是预处理阶段预处理完毕之后就是查询。由于树的高度是 $O(m)$m 为 words 的平均长度查询基本操作的次数不会大于 m同时基本操作次数也不会大于 kk 为被查询单词 keyword 的长度因此对于查询来说时间复杂度为 $O(min(m, k))$时间上优化的代价是空间上的消耗对于空间来说则是预处理的消耗空间复杂度为 $O(t)$。这正是空间换时间的典型体现。前缀树的特点简单来说前缀树就是一个树一般是将一系列的单词记录到树上。如果这些单词没有公共前缀则和直接用数组存储没有任何区别而如果有公共前缀则公共前缀仅会被存储一次。可以想象如果一系列单词的公共前缀很多则会有效减少空间消耗。前缀树的意义实际上是空间换时间这和哈希表、动态规划等的初衷是一样的。其原理也很简单公共前缀仅被存储一次因此想在堆单词中找某个单词或某个前缀是否出现无需进行完整遍历而是遍历前缀树即可。本质上使用前缀树和不使用前缀树减少的时间就是公共前缀的数目——也就是说如果一堆单词没有公共前缀使用前缀树就没有任何意义。知道了前缀树的特点接下来可以自己实现一个前缀树仓库中的实现参考 problems/208.implement-trie-prefix-tree.md。应用场景及分析前缀树的核心思想是用空间换时间利用字符串的公共前缀来降低查询的时间开销。场景一精确查找。给你一个字符串 query问这个字符串是否在字符串集合中出现过。可以将字符串集合建树建好之后来匹配 query 是否出现。有人可能会问之前讲过的 HashMap 岂不是更好这里需要理解的是上述精确查找只是模糊查找的一个特例。模糊查找 HashMap 显然做不到并且即便在精确查找问题中如果 HashMap 出现过多冲突效率也不一定比 Trie 高。场景二敏感词过滤。给你一个长句和一堆敏感词找出长句中所有敏感词出现的所有位置想一想有时候我们口吐芬芳结果发送出去却变成了****懂了吧。小提示实际上AC 自动机就利用了 Trie 的性质来实现敏感词的匹配性能非常好以至于很多编辑器都是用的 AC 自动机算法。场景三流式数据匹配。面对逐个到达的字符流需要在任意时刻判断最近若干字符是否构成字典中的单词直接的做法是每次扫描历史记录复杂度不可接受而倒序插入的 Trie 可以高效解决见下文 1032. 字符流 的分析。除此之外前缀树还可用于自动补全、拼写检查、最长公共前缀查询等场景这里不过多讨论。实战六道经典题解与模板变形前缀树题目的变化通常不大使用模板就可以解决。难点在于识别何时该用前缀树只要记住一点即可——算法的复杂度瓶颈在字符串查找并且字符串有很多公共前缀就可以用前缀树优化。下面结合仓库中的题解看看标准模板在不同题目中如何变形。208. 实现 Trie前缀树problems/208.implement-trie-prefix-tree.md 是这道题的标准题解题目要求实现insert、search和startsWith三个操作输入均由小写字母 a-z 构成且非空。为了区分search和startsWith需要增加一个标示区分当前节点是否是某个单词的结尾。因此题解中节点的数据结构为function TrieNode(val) { this.val val; // 当前的字母 this.children []; // 题目要求字典仅有a-z那么其长度最大为2626个字母 this.isWord false; }由于 children 是数组插入时需要通过一个函数计算字符对应的索引function computeIndex(c) { return c.charCodeAt(0) - a.charCodeAt(0); }insert、search和startsWith的逻辑都差不多从 root 出发找到需要操作的 child然后进行相应操作添加、修改、返回。insert时在每个字符节点上判断children[current]是否为空为空则创建新节点最后在末尾节点标记ws.isWord truesearch遍历完单词后直接返回ws.isWordstartsWith只要求路径存在遍历完前缀后返回true即可。这里isWord布尔标记与讲义模板中count 0的用法本质一致都是判断单词结尾的控制域。211. 添加与搜索单词通配符.problems/211.add-and-search-word-data-structure-design.md 要求支持添加单词和搜索单词其中搜索的word可能包含.每个.可以代表任何一个字母。如果不用 Trie直接在数组中线性查找复杂度会比较高使用前缀树后每次查找复杂度为 $O(h)$其中 h 是前缀树深度也就是最长的字符串长度。由于需要考虑特殊字符.需要对标准前缀树做一点改造insert不做改变只改变search。当遇到.时枚举当前节点的所有孩子将.替换为该孩子字符后递归搜索只要有一个分支能匹配成功即返回 TruePython 代码def search(self, word): Returns if the word is in the trie. :type word: str :rtype: bool curr self.Trie for i, w in enumerate(word): if w .: wizards [] for k in curr.keys(): if k #: continue wizards.append(self.search(word[:i] k word[i 1:])) return any(wizards) if w not in curr: return False curr curr[w] return # in curr对比标准的前缀树搜索无.def search(self, word): Returns if the word is in the trie. :type word: str :rtype: bool curr self.Trie for w in word: if w not in curr: return False curr curr[w] return # in curr可以看到该题解用 Python 字典实现 Triecurr[#] 1标记单词结尾替代了讲义中count/preCount的方案说明控制域的记录形式可以根据题目需要灵活选择。212. 单词搜索 IITrie DFS 剪枝problems/212.word-search-ii.md 要求在一个二维网格中找出同时出现在网格和字典中的所有单词。朴素思路是对矩阵中每一项都进行深度优先遍历DFS递归终点是超出边界或者递归路径上组成的单词不在 words 的前缀中。题目提示要优化回溯算法以通过更大数据量的测试并问什么样的数据结构可以有效地执行这样的操作散列表是否可行为什么前缀树如何——答案正是前缀树在 DFS 过程中用 Trie 快速判断当前路径是否为某个单词的前缀从而提前剪枝。比如 words [oath,pea,eat,rain]那么对于oa、oat来说它们满足条件都是 oath 的前缀有希望找到 oath但oaa就不满足条件可以立即剪掉。如果不剪枝则无法通过所有测试用例。具体实现注意两点如果每次 DFS 都用startsWith判断会超时。更好的做法是将当前遍历到的 trie 节点以参数传递到 dfs 中进一步减少复杂度使用set收集结果去重最后再转成 list 返回。关键代码如下Pythonfrom collections import defaultdict class Trie: def __init__(self): self.children defaultdict(Trie) self.word def insert(self, word): cur self for c in word: cur cur.children[c] cur.word word这里的 Trie 又一种变形用defaultdict(Trie)自动创建孩子节点并在节点上直接存放完整单词word而非布尔标记这样 DFS 到达某个节点时直接判断cur.word ! 即可取出命中单词。472. 连接词Trie 记忆化 排序剪枝problems/472.concatenated-words.md 要求返回给定单词列表中所有的连接词——一个完全由列表中至少两个其他单词组成的字符串。思路是先遍历一次将 words 全部插入前缀树再遍历一次查找每一个单词由几个单词表中的单词组成如果大于等于 2将其加入结果集。关键在于第二步查找每个单词由几个词组成。比如查找catsdogcats由于我们并不知道在cat处断开结果更大还是在cats处断开结果更大因此需要全部递归求出并取最大值。但直接递归可能会超时卡在最后一个测试用例上一个简单的方式是记忆化递归避免重复计算。而 2021-12-28 更新说明由于力扣增加了测试用例仅靠记忆化也无法 AC需要进一步优化——先将 words 按长度排序再对每个 word 判断如果它是合成词就没必要插入 trie不影响答案最多是 cntWords 计算出的数字不准确而题目只关心是否 2这样后续短词不会出现在前缀树中达到剪枝目的for word in words: if trie.cntWords(word) 2: res.append(word) else: trie.insert(word)注意一定要排序否则如果合成词在前就没有优化效果达不到剪枝的目的。核心的cntWords用递归 记忆化实现遇到字典中已有的单词结尾#时取1 cntWords(word[i1:])的最大值并将结果缓存到visited中。820. 单词的压缩编码倒序插入模拟后缀树problems/820.short-encoding-of-words.md 要求把单词列表编码成一个索引字符串 S以#分隔求最小长度。读完题目会发现如果把列表中的每个单词倒序这就变成了一个后缀树问题比如 [time, me, bell] 倒序后是 [emit, em, lleb]要求的结果无非是 emit 的长度 lleb 的长度 两个#的长度em 和 emit 有公共前缀只计算一个。因此符合直觉的做法是使用前缀树 倒序插入来模拟后缀树。同时需要考虑 edge case列表中包含重复元素如 [time, time, me, bell]使用 hashset 去重。实现要点插入时对word[::-1]倒序插入搜索时用len(curr) 1判断当前节点是否为单词结尾——当搜索em由me倒序而来时其节点下还有i分支说明me是time的后缀可以被time覆盖不单独计长度def search(self, word): Returns if the word is in the trie. :type word: str :rtype: bool curr self.Trie for w in word: curr curr[w] # len(curr) 1 means we meet # # when we search em(which reversed from me) # the result is len(curr) 1 # cause the curr look like { #: 1, i: {...}} return len(curr) 1最终对每个单词若它是其他单词的后缀倒序搜索返回 False 的被覆盖情形之外则累加len(word) 1。1032. 字符流倒序插入 双端队列problems/1032.stream-of-characters.md 要求实现StreamChecker每次query(letter)判断是否能用查询的最后 k 个字符按从旧到新顺序拼写出字词表中的某一单词。数据规模上 words 长度与单词长度均可达 2000、待查项最多 40000直接每次 query 扫描历史字符的复杂度为 $O(m \times n \times q)$毫无疑问会超时。解决思路是构建 Trie以空间换时间只需要对常规的search做一个简单修改不检查整个 word 是否存在而是检查以 word 为后缀的单词是否存在。具体算法init中构建 Trie 和双端队列 streamquery时往 stream 的左边 append 新字符调用改造后的 Trie 的 search。以示例为例当 query(c) 时需要查abc、bc、c三个是否有一个在 words 中。由于已知待查项的尾字符此例为 c因此从尾字符开始在前缀树中搜索即可这提示我们前缀树倒序插入或者 stream 倒序插入class StreamChecker: def __init__(self, words: List[str]): self.trie Trie() self.stream deque([]) for word in set(words): self.trie.insert(word[::-1])这里有两个细节需要注意如果用数组存储历史字符由于每次都往数组头部插入元素每次 query 的时间复杂度为 $O(N)$N 为截止当前的 query 次数应使用双端队列优化反序插入的技巧与 211. 添加与搜索单词 中的思路类似本质上都是让匹配从固定的一端开始。更多 Trie 相关题解仓库中还收录了其他与 Trie 相关的题目如 problems/1178.number-of-valid-words-for-each-puzzle.md猜字谜与 problems/5640.maximum-xor-with-an-element-from-array.md带异或运算的 Trie读者可在掌握基础模板后自行研究这些变体。总结前缀树的核心思想是用空间换时间利用字符串的公共前缀来降低查询的时间开销。因此如果题目中公共前缀比较多就可以考虑使用前缀树来优化。前缀树的基本操作就是插入和查询其中查询可以完整查询也可以前缀查询基于前缀的查询才是前缀树的灵魂也是其名字的来源。本文最后给出了 Java、Python、JavaScript 三种语言的前缀树模板大家如果需要用直接将其封装成标准 API 调用即可。基于前缀树的题目变化通常不大使用模板就可以解决。如何知道该使用前缀树优化是一个难点但只要牢牢记一点即可算法的复杂度瓶颈在字符串查找并且字符串有很多公共前缀就可以用前缀树优化。延伸阅读thinkings/trie.en.md前缀树专题英文版thinkings/DFS.md深度优先遍历配合 212. 单词搜索 II 食用更佳thinkings/island.md小岛专题二维网格 DFS 套路同样是 212 题 的前置知识。赞分享文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载相关推荐leetcode 题解仓库前缀树Trie专题从三语言模板到六大经典题型实战leetcode 题解仓库前缀树Trie专题从三语言模板到六大经典题型实战 导读 前缀树Prefix Tree又称字典树、Trie是一类以空间换时间文档教程知识库LeetCode-Go 题解精讲208. Implement Trie (Prefix Tree) —— 一份可复用的 Go 语言前缀树模板LeetCode Go 题解精讲208. Implement Trie Prefix Tree —— 一份可复用的 Go 语言前缀树模板 前缀树Trie是示例工程用 Go 实现 LeetCode 208Trie 前缀树模板与 insert / search / startsWith 全解用 Go 实现 LeetCode 208Trie 前缀树模板与 insert / search / startsWith 全解 本篇文章以 LeetCode示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考