LeetCode 642 设计搜索自动补全系统Design Search Autocomplete System难度Hard标签设计、字典树Trie、哈希表、排序、前缀匹配题目原文题目描述为搜索引擎设计一个自动补全系统。用户可以一条字符一条字符输入句子当输入特殊字符#代表本次输入结束。规则句子的热度hot degree该句子之前被完整输入的次数。用户每输入一个非#字符返回最多3条历史句子满足句子前缀和当前已经输入的字符串一致。返回结果排序规则优先按热度降序热度越高排在前面如果热度相同按ASCII字典升序字符串小的放前面符合条件不足3条有多少返回多少。如果输入字符是#代表本次输入结束把当前输入的句子存入系统如果句子已存在热度1不存在就新增热度1返回空列表并且清空本次输入缓存准备下一轮输入。你需要实现类AutocompleteSystem(sentences: List[str], times: List[int])构造函数传入初始历史句子数组和对应热度数组input(c: str) - List[str]用户输入单个字符c返回推荐列表示例# 初始化sentences[i love you,island,iroman,i love leetcode]times[5,3,2,2]objAutocompleteSystem(sentences,times)obj.input(i)# 输出[i love you, island, i love leetcode]obj.input( )# 输出[i love you, i love leetcode]obj.input(a)# 输出[] 没有前缀匹配句子obj.input(#)# 输出[]把句子i a加入系统热度变成1清空输入缓存约束说明句子由小写英文字母 空格构成每次input只传入单个字符构造函数的sentences数组不会重复。费曼学习法拆解本题用大白话讲给小白第一步一句话理解题目要做什么模拟百度/谷歌搜索框用户敲字母实时弹出3条搜索推荐。敲完句子按回车本题用#代替回车系统记住这条搜索下次再输入相同前缀这条搜索就会参与推荐搜索次数越多排名越靠前。核心难点前缀快速匹配 →字典树Trie专门用来存字符串前缀维护每个句子的全局热度每次查询前缀后拿到候选句子按规则排序取Top3状态管理用户正在输入的字符串缓存遇到#重置缓存更新热度。Trie字典树原理通俗解释字典树是树形结构每个节点代表一个字符。句子i love youi→空格→l→o→v…一路往下走。关键技巧每一个Trie节点保存所有经过这个节点的完整句子。只要走到某个节点代表用户输入的前缀到这里节点里存的全部句子都是匹配当前前缀的候选句子。举例子输入i走到字符i对应的Trie节点这个节点保存所有以i开头的句子i love you、island、iroman、i love leetcode。然后拿这4条句子根据热度排序选出前3。第二步两种解法思路对比解法1基础字典树Trie 全局热度字典面试首选代码直观好理解思路全局哈希表freqkey句子value热度记录每一条句子被搜索多少次Trie树每个节点包含子节点映射以及一个集合保存所有经过当前节点的完整句子构造函数遍历初始sentences把每个句子插入Trie同时写入freq维护curr_input数组保存用户当前正在敲的字符input(c)逻辑如果c #拼接curr_input为完整句子freq里热度1重新插入Trie清空curr_input返回[]普通字符追加到curr_input沿着Trie往下走如果中途找不到子节点后面输入永远没有匹配直接返回空找到节点取出节点里全部句子根据(-热度,句子)排序取前3。✅优点逻辑清晰面试手写不容易错❌缺点每次查询要排序候选句子句子数量很大的时候排序开销大。解法2优化Trie节点节点内维护Top3进阶优化思路Trie的每一个节点不保存全部候选句子直接维护已经排好序的Top3。插入句子时更新路径上所有节点的top3列表。查询的时候直接返回节点预存好的top3不用每次排序。✅优点查询速度O(1)适合线上搜索引擎❌缺点插入逻辑复杂面试写代码耗时更长容易写出bug。本题面试场景优先写解法1能一次AC面试官看懂。第三步坑点排查费曼找漏洞坑1**空格也是合法字符**不能忽略空格空格和字母同等对待作为Trie节点的key。坑2排序key(-热度,句子)负号实现热度降序热度相同字符串升序。坑3遇到#新句子必须插入Trie后续输入前缀要能搜到这条新增句子。坑4如果走到Trie中途发现没有子节点后续再输入字符永远没有匹配结果。坑5句子可以重复输入热度累加。第四步现实应用场景举例搜索引擎搜索框自动提示百度、谷歌输入关键词实时下拉推荐根据用户历史搜索次数排序输入法联想词拼音输入给出候选词组高频词优先代码编辑器自动补全IDE输入函数前缀推荐历史高频函数名电商搜索框淘宝京东输入商品名称推荐热门搜索词。Python代码实现解法1 Trie基础版每行详细注释fromtypingimportList# 定义字典树节点类classTrieNode:def__init__(self):# children字典key是字符value是子TrieNodeself.childrendict()# sentences集合保存所有经过当前节点的完整句子self.sentencesset()classAutocompleteSystem:def__init__(self,sentences:List[str],times:List[int]):# 初始化字典树根节点self.rootTrieNode()# freq全局哈希表记录每个句子的热度key句子value热度self.freq{}# curr_input缓存用户当前正在输入的字符列表逐字符追加self.curr_input[]# curr_node记录当前Trie走到哪个节点初始指向根节点self.curr_nodeself.root# 遍历初始化历史句子和热度forsent,hotinzip(sentences,times):self.freq[sent]hot# 将句子插入字典树self._insert_sentence(sent)def_insert_sentence(self,sentence:str):私有函数把完整句子插入Trie树nodeself.root# 遍历句子每一个字符forcharinsentence:# 如果当前字符不在子节点新建节点ifcharnotinnode.children:node.children[char]TrieNode()# 移动到子节点nodenode.children[char]# 当前节点加入这个句子所有前缀节点都保存这条句子node.sentences.add(sentence)definput(self,c:str)-List[str]:用户输入单个字符c返回top3推荐句子# 情况1输入#本次句子结束ifc#:# 把当前缓存的字符拼接成完整句子full_sent.join(self.curr_input)# 更新热度存在则1不存在初始化为1iffull_sentinself.freq:self.freq[full_sent]1else:self.freq[full_sent]1# 将新句子插入Trie树后续查询可以搜到self._insert_sentence(full_sent)# 清空本次输入缓存重置当前节点到根准备新一轮输入self.curr_input[]self.curr_nodeself.root# #输入直接返回空列表return[]# 情况2普通字符追加到当前输入缓存self.curr_input.append(c)# 判断当前节点有没有这个字符的子节点ifcnotinself.curr_node.children:# 没有匹配分支后续输入永远没有候选curr_node置None标记self.curr_nodeNone# 没有匹配前缀返回空列表return[]# 存在子节点移动到子节点self.curr_nodeself.curr_node.children[c]# 获取当前节点保存的全部候选句子candidate_sentsself.curr_node.sentences# 排序规则-self.freq[x]热度降序x字典升序热度相同sorted_candidatessorted(candidate_sents,keylambdax:(-self.freq[x],x))# 取前3个返回returnsorted_candidates[:3]# 测试样例 if__name____main__:# 初始化历史数据sentences[i love you,island,iroman,i love leetcode]times[5,3,2,2]autoAutocompleteSystem(sentences,times)print(auto.input(i))# [i love you, island, i love leetcode]print(auto.input( ))# [i love you, i love leetcode]print(auto.input(a))# []print(auto.input(#))# [] 句子i a存入系统# 再输入i 空格 a就能看到新句子i a被推荐print(auto.input(i))print(auto.input( ))print(auto.input(a))进阶优化版本Trie节点预存Top3减少每次排序开销fromtypingimportListclassTrieNode:def__init__(self):self.childrendict()# 节点维护top3列表保存(热度,句子)元组不用每次查询全量排序self.top3[]classAutocompleteSystem:def__init__(self,sentences:List[str],times:List[int]):self.rootTrieNode()self.freq{}self.curr_input[]self.curr_nodeself.rootforsent,hotinzip(sentences,times):self.freq[sent]hot self._insert(sent)def_insert(self,sentence):nodeself.root hotself.freq[sentence]forcharinsentence:ifcharnotinnode.children:node.children[char]TrieNode()nodenode.children[char]# 添加新记录去重new_item(hot,sentence)temp_list[]existFalseforh,sinnode.top3:ifssentence:temp_list.append(new_item)existTrueelse:temp_list.append((h,s))ifnotexist:temp_list.append(new_item)# 排序热度降序句子升序截断保留前3temp_list.sort(keylambdax:(-x[0],x[1]))node.top3temp_list[:3]definput(self,c:str)-List[str]:ifc#:full_sent.join(self.curr_input)self.freq[full_sent]self.freq.get(full_sent,0)1self._insert(full_sent)self.curr_input[]self.curr_nodeself.rootreturn[]self.curr_input.append(c)ifself.curr_nodeisNoneorcnotinself.curr_node.children:self.curr_nodeNonereturn[]self.curr_nodeself.curr_node.children[c]# 直接取出top3句子return[sentforhot,sentinself.curr_node.top3]# 测试if__name____main__:sentences[i love you,island,iroman,i love leetcode]times[5,3,2,2]autoAutocompleteSystem(sentences,times)print(auto.input(i))print(auto.input( ))print(auto.input(a))print(auto.input(#))复杂度分析基础Trie解法构造函数O(total_length)所有句子字符总长度input普通字符O(L M log M)L是字符移动开销M是当前前缀匹配的候选句子数量排序input遇到#O(S)S是新句子长度插入Trie。Top3预存优化版查询阶段O(1)查询速度大幅提升插入句子时路径上每个节点都要重新排序插入开销增加。费曼复盘总结这道Hard设计题核心是字典树Trie。Trie专门解决前缀匹配。两个关键点每一条句子插入的时候这条句子要放到路径上所有节点排序规则(-热度,句子)负号实现热度降序同热度字典序升序。面试如果遇到优先写基础版本代码简单不容易bug。