图解 LeetCode 第 642 号问题：搜索自动完成系统
总第61篇/程序员小吴
LeetCode上第 642 号问题：Design Search Autocomplete System
题目描述
为搜索引擎设计一个搜索自动完成系统。用户可以输入一个句子(至少一个单词，并以一个特殊的字符'#'结尾)。对于除'#'之外的每个字符，您需要返回与已输入的句子部分前缀相同的前3个历史热门句子。具体规则如下:
一个句子的热度定义为用户输入完全相同句子的次数。 返回的前3个热门句子应该按照热门程度排序(第一个是最热的)。如果几个句子的热度相同，则需要使用ascii代码顺序(先显示较小的一个)。 如果少于3个热门句子，那么就尽可能多地返回。 当输入是一个特殊字符时，它意味着句子结束，在这种情况下，您需要返回一个空列表。 您的工作是实现以下功能:
构造函数:
AutocompleteSystem(String[] sentence, int[] times):这是构造函数。输入是历史数据。句子是由之前输入的句子组成的字符串数组。Times是输入一个句子的相应时间。您的系统应该记录这些历史数据。
现在，用户想要输入一个新句子。下面的函数将提供用户类型的下一个字符:
Listinput(char c):输入c是用户输入的下一个字符。字符只能是小写字母(“a”到“z”)、空格(“”)或特殊字符(“#”)。另外，前面输入的句子应该记录在系统中。输出将是前3个历史热门句子，它们的前缀与已经输入的句子部分相同。
例子: 操作:AutocompleteSystem(["i love you"， "island"，"ironman"， "i love leetcode"]， [5,3,2,2]) 系统已经追踪到以下句子及其对应的时间:
"i love you" : 5 times "island" : 3 times "ironman" : 2 times "i love leetcode" : 2 times
现在，用户开始另一个搜索:
操作:输入(“i”) 输出:["i love you"， "island"，"i love leetcode"] 解释: 有四个句子有前缀“i”。其中，《ironman》和《i love leetcode》有着相同的热度。既然“ ” ASCII码为32，“r”ASCII码为114，那么“i love leetcode”应该在“ironman”前面。此外，我们只需要输出前3个热门句子，所以“ironman”将被忽略。
操作:输入(' ') 输出:[“i love you”，“i love leetcode”] 解释: 只有两个句子有前缀“i”。
操作:输入(' a ') 输出:[] 解释: 没有以“i a”为前缀的句子。
操作:输入(“#”) 输出:[] 解释: 用户完成输入后，在系统中将句子“i a”保存为历史句。下面的输入将被计算为新的搜索。
注意:
输入的句子总是以字母开头，以“#”结尾，两个单词之间只有一个空格。 要搜索的完整句子不会超过100个。包括历史数据在内的每句话的长度不会超过100句。 在编写测试用例时，即使是字符输入，也请使用双引号而不是单引号。 请记住重置在AutocompleteSystem类中声明的类变量，因为静态/类变量是跨多个测试用例持久化的。详情请点击这里。
题目大意：
设计一个搜索自动补全系统，它需要包含如下两个方法：
构造方法：
AutocompleteSystem(String[] sentences, int[] times): 输入句子sentences，及其出现次数times
输入方法：
Listinput(char c): 输入字符c可以是26个小写英文字母，也可以是空格，以'#'结尾。返回输入字符前缀对应频率最高的至多3个句子，频率相等时按字典序排列。
思路解析：
核心点：Trie（字典树）
利用字典树记录所有出现过的句子集合，利用字典保存每个句子出现的次数。
解题思路
题目的要求是补全的句子是按之前出现的频率排列的，高频率的出现在最上面，如果频率相同，就按字母顺序来显示。
频率 这种要求很容易想到 堆、优先队列、树、Map等知识点，这里涉及到 字典 与 树，那肯定使用 字典树 能解决。
所以首先构造 Trie 的 trieNode 结构以及 insert 方法，构造完 trieNode 类后，再构造一个树的根节点。
由于每次都要输入一个字符，我们可以用一个私有的 Node：curNode 来追踪当前的节点。
curNode 初始化为 root ，在每次输入完一个句子时，即输入的字符为‘#’时，我们需要将其置为root。
同时还需要一个 string 类型 stn 来表示当前的搜索的句子。
每输入一个字符，首先检查是不是结尾标识“#”，如果是的话，将当前句子加入trie树，重置相关变量，返回空数组。
- 如不是，检查当前 TrieNode 对应的 child 是否含有 c 的对应节点。如果没有，将 curNode 置为 NULL 并且返回空数组。
- 若存在，将curNode 更新为c对应的节点，并且对curNode进行dfs。
dfs 时，我们首先检查当前是不是一个完整的句子，如果是，将句子与其次数同时加入 priority_queue 中，然后对其 child 中可能存在的子节点进行 dfs 。
进行完 dfs 后，只需要取出前三个，需要注意的是，可能可选择的结果不满3个，所以要在 while 中多加入检测 q 为空的条件语句。
最后要将 q 中的所有元素都弹出。
动画演示
动画是使用 AE 制作，因此体积比较大，有 32 M，无法使用GIF播放，因此采取视频播放形式，手机党慎点：）
感谢 Jun Chen 大佬提供动画技术支持，笔芯。
参考代码
C++
1class TrieNode{
2 public:
3 string str;
4 int cnt;
5 unordered_map<char, TrieNode*> child;
6 TrieNode(): str(""), cnt(0){};
7};
8
9struct cmp{
10 bool operator() (const pair<string, int> &p1, const pair<string, int> &p2){
11 return p1.second < p2.second || (p1.second == p2.second && p1.first > p2.first);
12 }
13};
14
15class AutocompleteSystem {
16public:
17 AutocompleteSystem(vector<string> sentences, vector<int> times) {
18 root = new TrieNode();
19 for(int i = 0; i < sentences.size(); i++){
20 insert(sentences[i], times[i]);
21 }
22 curNode = root;
23 stn = "";
24 }
25
26 vector<string> input(char c) {
27 if(c == '#'){
28 insert(stn, 1);
29 stn.clear();
30 curNode = root;
31 return {};
32 }
33 stn.push_back(c);
34 if(curNode && curNode->child.count(c)){
35 curNode = curNode->child[c];
36 }else{
37 curNode = NULL;
38 return {};
39 }
40
41 dfs(curNode);
42
43 vector<string> ret;
44 int n = 3;
45 while(n > 0 && !q.empty()){
46 ret.push_back(q.top().first);
47 q.pop();
48 n--;
49 }
50 while(!q.empty()) q.pop();
51
52 return ret;
53 }
54
55 void dfs(TrieNode* n){
56 if(n->str != ""){
57 q.push({n->str, n->cnt});
58 }
59 for(auto p : n->child){
60 dfs(p.second);
61 }
62 }
63
64 void insert(string s, int cnt){
65 TrieNode* cur = root;
66 for(auto c : s){
67 if(cur->child.count(c) == 0){
68 cur->child[c] = new TrieNode();
69 }
70 cur = cur->child[c];
71 }
72 cur->str = s;
73 cur->cnt += cnt;
74 }
75
76private:
77 TrieNode *root, *curNode;
78 string stn;
79 priority_queue<pair<string,int>, vector<pair<string, int>>, cmp > q;
80
81};Python
1class TrieNode:
2 def __init__(self):
3 self.children = dict()
4 self.sentences = set()
5
6class AutocompleteSystem(object):
7
8 def __init__(self, sentences, times):
9 """
10 :type sentences: List[str]
11 :type times: List[int]
12 """
13 self.buffer = ''
14 self.stimes = collections.defaultdict(int)
15 self.trie = TrieNode()
16 for s, t in zip(sentences, times):
17 self.stimes[s] = t
18 self.addSentence(s)
19 self.tnode = self.trie
20
21 def input(self, c):
22 """
23 :type c: str
24 :rtype: List[str]
25 """
26 ans = []
27 if c != '#':
28 self.buffer += c
29 if self.tnode: self.tnode = self.tnode.children.get(c)
30 if self.tnode: ans = sorted(self.tnode.sentences, key=lambda x: (-self.stimes[x], x))[:3]
31 else:
32 self.stimes[self.buffer] += 1
33 self.addSentence(self.buffer)
34 self.buffer = ''
35 self.tnode = self.trie
36 return ans
37
38 def addSentence(self, sentence):
39 node = self.trie
40 for letter in sentence:
41 child = node.children.get(letter)
42 if child is None:
43 child = TrieNode()
44 node.children[letter] = child
45 node = child
46 child.sentences.add(sentence)代码截图
C++代码
腾讯云开发者
