> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/trie/642.-design-search-autocomplete-system.md). # 642. Design Search Autocomplete System Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character `'#'`). For **each character** they type **except '#'**, you need to return the **top 3** historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules: 1. The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before. 2. The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first). 3. If less than 3 hot sentences exist, then just return as many as you can. 4. When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list. Your job is to implement the following functions: The constructor function: `AutocompleteSystem(String[] sentences, int[] times):` This is the constructor. The input is **historical data**. `Sentences` is a string array consists of previously typed sentences. `Times` is the corresponding times a sentence has been typed. Your system should record these historical data. Now, the user wants to input a new sentence. The following function will provide the next character the user types: `List input(char c):` The input `c` is the next character typed by the user. The character will only be lower-case letters (`'a'` to `'z'`), blank space (`' '`) or a special character (`'#'`). Also, the previously typed sentence should be recorded in your system. The output will be the **top 3** historical hot sentences that have prefix the same as the part of sentence already typed. **Example:**\ **Operation:** AutocompleteSystem(\["i love you", "island","ironman", "i love leetcode"], \[5,3,2,2])\ The system have already tracked down the following sentences and their corresponding times:\ `"i love you"` : `5` times\ `"island"` : `3` times\ `"ironman"` : `2` times\ `"i love leetcode"` : `2` times\ Now, the user begins another search:\ \ **Operation:** input('i')\ **Output:** \["i love you", "island","i love leetcode"]\ **Explanation:**\ There are four sentences that have prefix `"i"`. Among them, "ironman" and "i love leetcode" have same hot degree. Since `' '` has ASCII code 32 and `'r'` has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.\ \ **Operation:** input(' ')\ **Output:** \["i love you","i love leetcode"]\ **Explanation:**\ There are only two sentences that have prefix `"i "`.\ \ **Operation:** input('a')\ **Output:** \[]\ **Explanation:**\ There are no sentences that have prefix `"i a"`.\ \ **Operation:** input('#')\ **Output:** \[]\ **Explanation:**\ The user finished the input, the sentence `"i a"` should be saved as a historical sentence in system. And the following input will be counted as a new search. **Note:** 1. The input sentence will always start with a letter and end with '#', and only one blank space will exist between two words. 2. The number of **complete sentences** that to be searched won't exceed 100. The length of each sentence including those in the historical data won't exceed 100. 3. Please use double-quote instead of single-quote when you write test cases even for a character input. 4. Please remember to **RESET** your class variables declared in class AutocompleteSystem, as static/class variables are **persisted across multiple test cases**. Please see [here](https://leetcode.com/faq/#different-output) for more details. 设计自动补全系统，初始时有一系列候选句子和对应的频次，当输入一个字符后给出当前所输入所有字符串作为前缀后的频次最高的三个候选句子，当输入#后把当前缓存看作候选句子并清空缓存。查词用trie或hash map。把每个句子输入进trie时让trie的每个对应前缀结点记录下这个句子和出现的频次，为了能更新频次，将句子和频次打包成一个类然后用hash map记录所有的句子类。将每个输入的字符记录下来，并在trie中搜索当前的所有输入是否存在，并把遍历到的trie结点里存的句子排序后输出前三。遇到#后更新hash map，如果是新句再继续遍历并更新trie。 ```cpp class AutocompleteSystem { public: class Word { public: int freq; string w; Word(string w_, int freq_): w(w_), freq(freq_) {} }; class TrieNode { public: vector s; unordered_map children; TrieNode() {} }; unordered_map words; void add(string sentence, int times) { if (!words.count(sentence)) { words[sentence] = new Word(sentence, times); auto w = words[sentence]; auto cur = root; for (const auto c : sentence) { if (cur->children[c] == nullptr) cur->children[c] = new TrieNode(); cur = cur->children[c]; cur->s.push_back(w); } } else ++words[sentence]->freq; } TrieNode *root, *cur; AutocompleteSystem(vector& sentences, vector& times) { root = new TrieNode(); for (int i = 0; i < sentences.size(); ++i) add(sentences[i], times[i]); cur = root; } string ss; vector input(char c) { vector res; if (c == '#') { add(ss, 1); ss.clear(); cur = root; return res; } ss += c; if (cur == nullptr) return res; cur = cur->children[c]; if (cur == nullptr) return res; const auto cmp = [](const Word *a, const Word *b) { if (a->freq != b->freq) return a->freq > b->freq; return a->w < b->w; }; priority_queue, decltype(cmp)> pq(cmp); for (auto t : cur->s) { pq.push(t); if (pq.size() > 3) pq.pop(); } while (!pq.empty()) { res.push_back(pq.top()->w); pq.pop(); } reverse(res.begin(), res.end()); return res; } }; /** * Your AutocompleteSystem object will be instantiated and called as such: * AutocompleteSystem* obj = new AutocompleteSystem(sentences, times); * vector param_1 = obj->input(c); */ ``` ```python class AutocompleteSystem: def insert(self, w: str, t=1): cur = self.root for c in w: if c not in cur: cur[c] = {} cur = cur[c] if 'hot' not in cur: cur['hot'] = {} if w not in cur['hot']: cur['hot'][w] = 0 cur['hot'][w] += t def __init__(self, sentences: List[str], times: List[int]): self.root = {} self.w = '' self.cur = self.root for i, s in enumerate(sentences): self.insert(s, times[i]) def input(self, c: str) -> List[str]: if c == '#': self.insert(self.w) self.w = '' self.cur = self.root return [] self.w += c if self.cur == None or c not in self.cur: self.cur = None return [] self.cur = self.cur[c] return [k for k, v in sorted(self.cur['hot'].items(), key=lambda x: (-x[1], x[0]), reverse=False)][0:3] # Your AutocompleteSystem object will be instantiated and called as such: # obj = AutocompleteSystem(sentences, times) # param_1 = obj.input(c) ```