[LeetCode]Design Search Autocomplete System

题目链接

这道题的要求可以分为两个部分：

• 首先根据输入的所有字符串和频率我们需要能够记录下来，然后在user输入每一个新字符的时候，我们要找到所有以这个prefix开头的字符串然后返回按照出现频率从高到低的前三个热词
• 之后对于每一个user新输入的词(以#结尾)，我们也需要动态地更新我们已有的数据

解决这个问题的思路就是用Trie，对于每一个节点，我们存所有以这个prefix开头的词。每次查询的时候，我们找到对应的节点，然后返回出现频率的前三个即可，之后在插入完整的词到trie当中更新即可。假设初始输入n个词，平均长度为m，查询字符串的长度为k，那么初始化的时间复杂度为O(m * n)，查询的时间复杂度为O(k)。空间复杂度的话，因为每一次会在其经过的所有节点上存一份，也就是m份，每一份长度为m，而总共有n个这样的词，所以总的空间复杂度为O(n * m^2)。代码如下：

	struct Node
	{
	vector<pair<int, string>> sentences;
	unordered_map<char, Node*> children;
	};
	class AutocompleteSystem {
	public:
	AutocompleteSystem(vector<string> sentences, vector<int> times) {
	root = new Node();
	int len = sentences.size();
	for(int i = 0; i < len; ++i)
	insert(sentences[i], times[i]);
	curr = root;
	}
	~AutocompleteSystem()
	{
	del(root);
	}
	vector<string> input(char c) {
	if(c == '#')
	{
	curr = root;
	insert(typed, 1);
	typed = "";
	return {};
	}
	typed += c;
	if(!curr)return {};
	//don't use curr = curr->children[c] and check if curr is nullptr
	//that will add {c, nullptr} to the children map
	if(curr->children.find(c) == curr->children.end())
	{
	curr = nullptr;
	return {};
	}
	curr = curr->children[c];
	int len = curr->sentences.size();
	vector<string> res;
	for(int i = 0; i < min(3, len); ++i)
	res.push_back(curr->sentences[i].second);
	return res;
	}
	private:
	Node* root, *curr;
	string typed;
	void insert(const string& sentence, int time)
	{
	int len = sentence.size();
	Node* curr = root;
	for(int i = 0; i < len; ++i)
	{
	char c = sentence[i];
	if(curr->children.find(c) == curr->children.end())
	curr->children[c] = new Node();
	update(curr, sentence, time);
	curr = curr->children[c];
	}
	//update terminal node
	update(curr, sentence, time);
	}
	void del(Node* curr)
	{
	if(!curr)return;
	for(auto& pair : curr->children)
	del(pair.second);
	delete curr;
	}
	void update(Node* curr, const string& sentence, int time)
	{
	if(curr == root)return;
	auto iter = find_if(curr->sentences.begin(), curr->sentences.end(), [sentence](const pair<int, string>& entry)
	{
	return entry.second == sentence;
	});
	if(iter != curr->sentences.end())
	++iter->first;
	else
	curr->sentences.emplace_back(time, sentence);
	auto comp = [](const pair<int, string>& lhs, const pair<int, string>& rhs)
	{
	return lhs.first == rhs.first? lhs.second < rhs.second : lhs.first > rhs.first;
	};
	sort(curr->sentences.begin(), curr->sentences.end(), comp);
	}
	};
	/**
	* Your AutocompleteSystem object will be instantiated and called as such:
	* AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
	* vector<string> param_1 = obj.input(c);
	*/

view raw Design Search Autocomplete System.cpp hosted with ❤ by GitHub