海量字符串快速前缀查询(Trie 思路)
哪些公司问过
答案要点
- 用 Trie 存储所有字符串,节点带结束标记和经过计数
- 查询按前缀字符逐层下走,复杂度 O(前缀长度),与串数量无关
- 统计数量看节点计数,列出匹配串则从该节点 DFS
- 字符集小用数组、大用哈希表存子节点,或用压缩前缀树省内存
- 替代方案:排序后二分查找前缀范围;数据量过大可按前缀分片
易错点
- 每个节点都开大数组,字符集大时内存爆炸
- 忘记结束标记,无法区分完整单词和前缀
- 用哈希存所有前缀,空间开销远大于 Trie
面试官常见追问
- Trie 内存占用大怎么优化?
- 怎么返回某前缀下热度最高的前 K 个词?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场