设计搜索自动补全系统
Design Search Autocomplete System
题目详情
问题：设计搜索自动补全系统
考察：字符串、设计、Trie 前缀树
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/design-search-autocomplete-system
Problem: Design Search Autocomplete System
Patterns: String, Design, Trie
Recency: 2yr
Link: https://leetcode.com/problems/design-search-autocomplete-system
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：使用 Trie 存储历史句子，每个节点维护经过该前缀的候选句子及热度。输入字符时沿 Trie 下移并返回热度高、字典序小的前三项；输入 # 时把当前句子写回 Trie。
复杂度：输入查询与前缀长度和候选维护方式相关；若每节点保留前三项，单字符查询可接近 O(1)。