Trie题目汇总

摘要: Trie 的题目总结

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

Trie 基本功能的思想和实现

参考文章：Trie

题目	备注
208. 实现 Trie (前缀树)	Trie 的插入，查找单词和前缀是否存在
211. 添加与搜索单词 - 数据结构设计	Trie 中的搜索

基于字典树的串上搜索

题目	备注
212. 单词搜索 II	Trie + DFS
720. 词典中最长的单词	Trie + DFS
425. 单词方块	Trie + DFS 【搜索难题】力扣425-单词方块
745. 前缀和后缀搜索	单 Trie 节点同时维护前缀后缀，哈希表维护子节点 双向Trie
1065. 字符串的索引对	单串多模式匹配
1410. HTML 实体解析器	单串多模式匹配，模式开头为统一特殊字符

基于字典树的设计

题目	备注
642. 设计搜索自动补全系统	Trie 需要把所有子树都遍历完成才能得到所有满足特定前缀的句子，由于这一点，效率不如哈希表。 【设计难题】力扣642-设计搜索自动补全系统
1268. 搜索推荐系统	单串多模式匹配
1032. 字符流	单串多模式匹配
676. 实现一个魔法字典	Trie + DFS
588. 设计内存文件系统	设计内存文件系统：平衡树TreeMap维护子节点的Trie
1233. 删除子文件夹	Trie + DFS

字典树与字典序

参考文章：用字典树处理字典序的问题

• 440. 字典序的第K小数字
• 386. 字典序排数

基于字典树的串上统计

题目	备注
677. 键值映射	节点带 value 字段
648. 单词替换	查询最短匹配的前缀
820. 单词的压缩编码	对 Trie 节点做常规的 N 叉树统计
421. 数组中两个数的最大异或值	字符只有10，01Trie + 位运算; 若动态区间查询，用可持久化字典树
527. 单词缩写	【多维分桶】力扣527-单词缩写

---