LeetCode 642. 设计搜索自动补全系统（Trie树）

Michael阿明

发布于 2021-02-19 10:29:38

1K0

发布于 2021-02-19 10:29:38

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

为搜索引擎设计一个搜索自动补全系统。用户会输入一条语句（最少包含一个字母，以特殊字符 ‘#’ 结尾）。除 ‘#’ 以外用户输入的每个字符，返回历史中热度前三并以当前输入部分为前缀的句子。下面是详细规则：

一条句子的热度定义为历史上用户输入这个句子的总次数。
返回前三的句子需要按照热度从高到低排序（第一个是最热门的）。如果有多条热度相同的句子，请按照 ASCII 码的顺序输出（ASCII 码越小排名越前）。
如果满足条件的句子个数少于 3，将它们全部输出。
如果输入了特殊字符，意味着句子结束了，请返回一个空集合。

你的工作是实现以下功能：

构造函数：

AutocompleteSystem(String[] sentences, int[] times): 这是构造函数，输入的是历史数据。 Sentences 是之前输入过的所有句子，Times 是每条句子输入的次数，你的系统需要记录这些历史信息。

现在，用户输入一条新的句子，下面的函数会提供用户输入的下一个字符：

List<String> input(char c): 其中 c 是用户输入的下一个字符。字符只会是小写英文字母（‘a’ 到 ‘z’ ），空格（' '）和特殊字符（'#'）。输出历史热度前三的具有相同前缀的句子。

样例 ：
操作 ： AutocompleteSystem(["i love you", 
"island","ironman", "i love leetcode"], 
[5,3,2,2])
系统记录下所有的句子和出现的次数：
"i love you" : 5 次
"island" : 3 次
"ironman" : 2 次
"i love leetcode" : 2 次
现在，用户开始新的键入：


输入 ： input('i')
输出 ： ["i love you", "island","i love leetcode"]
解释 ：
有四个句子含有前缀 "i"。其中 "ironman" 
和 "i love leetcode" 有相同的热度，
由于 ' ' 的 ASCII 码是 32 而 'r' 的 ASCII 码是 114，
所以 "i love leetcode" 在 "ironman" 前面。
同时我们只输出前三的句子，所以 "ironman" 被舍弃。

输入 ： input(' ')
输出 ： ["i love you","i love leetcode"]
解释:
只有两个句子含有前缀 "i "。

输入 ： input('a')
输出 ： []
解释 ：
没有句子有前缀 "i a"。

输入 ： input('#')
输出 ： []
解释 ：

用户输入结束，"i a" 被存到系统中，后面的输入被认为是下一次搜索。

注释：输入的句子以字母开头，以 ‘#’ 结尾，两个字母之间最多只会出现一个空格。即将搜索的句子总数不会超过 100。每条句子的长度（包括已经搜索的和即将搜索的）也不会超过 100。即使只有一个字母，输出的时候请使用双引号而不是单引号。请记住清零 AutocompleteSystem 类中的变量，因为静态变量、类变量会在多组测试数据中保存之前结果。详情请看这里。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/design-search-autocomplete-system 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

class trie
{
public:
	unordered_map<char, trie*> next;
	string word;//记录单词
	int freq = 0;//是单词时，记录频数
	void insert(string& s, int time)
	{
		trie *cur = this;
		for(int i = 0; i < s.size(); ++i)
		{
			if(!cur->next.count(s[i]))
				cur->next[s[i]] = new trie();
			cur = cur->next[s[i]];
		}
		cur->word = s;
		cur->freq += time;
	}
	void find(trie* cur, vector<pair<int, string>> &freq_wd)
	{
		if(!cur) return;
		if(cur->freq)//找到单词，存入候选集合
			freq_wd.push_back({cur->freq, cur->word});
		for(auto item : cur->next)
			find(item.second, freq_wd);
	}
};
class AutocompleteSystem {
	trie* t, *cur;
	string prefix;
public:
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
    	t = new trie();
    	cur = t;
    	for(int i = 0; i < sentences.size(); ++i)
    		t->insert(sentences[i], times[i]);
    }
    
    vector<string> input(char c) {
    	if(c == '#')
    	{
    		t->insert(prefix, 1);//单词记录+1次
    		prefix = "";
    		cur = t;
    		return {};
    	}
    	else
    	{
    		prefix += c;
    		if(!cur->next.count(c))
				cur->next[c] = new trie();
			cur = cur->next[c];
			vector<pair<int, string>> freq_wd;
			t->find(cur, freq_wd);
			sort(freq_wd.begin(), freq_wd.end(),[&](auto a, auto b){
				if(a.first == b.first)
					return a.second < b.second;
				return a.first > b.first;
			});//排序，取前3
			vector<string> ans;
			for(int i = 0; i < min(3, int(freq_wd.size())); ++i)
				ans.push_back(freq_wd[i].second);
			return ans;
    	}
    }
};

1040 ms 238.7 MB

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

ascii