# 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<String> 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.&#x20;

**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.&#x20;

**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.

```cpp
// Naive hashmap design
class AutocompleteSystem {
public:
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) : data("") {
        for (int i = 0; i < sentences.size(); ++i) {
            freq[sentences[i]] += times[i];
        }
    }
    
    vector<string> input(char c) {
        if (c == '#') {
            ++freq[data];
            data.clear();
            return {};
        }
        data.push_back(c);
        auto cmp = [] (const pair<string, int>& a, const pair<string, int>& b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        };
        // minHeap
        priority_queue<pair<string, int>, vector<pair<string, int> >, decltype(cmp)> pq(cmp);
        for (auto& f : freq) {
            bool matched = true;
            for (int i = 0; i < data.size(); ++i) {
                if (data[i] != f.first[i]) {
                    matched = false;
                    break;
                }
            }
            if (matched) {
                pq.push(f);
                if (pq.size() > 3) {
                    pq.pop();
                }
            }
        }
        vector<string> res(pq.size(), "");
        for (int i = pq.size() - 1; i >= 0; --i) {
            res[i] = pq.top().first;
            pq.pop();
        }
        return res;
    }
private:
    string data;
    unordered_map<string, int> freq;
};
```

```cpp
class AutocompleteSystem {
public:
    class TrieNode {
    public:
        TrieNode() {}
        ~TrieNode() {
            for (auto& child : children) {
                if (child.second) delete child.second;
            }
        }
        unordered_map<char, TrieNode*> children;
        unordered_map<string, int> count;
    };
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
        root = new TrieNode();
        prefix = "";
        for (int i = 0; i < sentences.size(); ++i) {
            add(sentences[i], times[i]);
        }
    }
    ~AutocompleteSystem() {
        delete root;
    }
    void add(const string& str, const int cnt) {
        TrieNode* cur = root;
        for (char ch : str) {
            if (!cur->children[ch]) {
                cur->children[ch] = new TrieNode();
            }
            cur = cur->children[ch];
            cur->count[str] += cnt;
        }
    }
    vector<string> input(char c) {
        if (c == '#') {
            add(prefix, 1);
            prefix.clear();
            return {};
        }
        prefix.push_back(c);
        TrieNode* cur = root;
        for (char ch : prefix) {
            if (!cur->children[ch]) return {};
            cur = cur->children[ch];
        }
        
        // auto cmp = [] (const pair<string, int>& a, const pair<string, int>& b) {
        //     return a.second < b.second || (a.second == b.second && a.first > b.first);
        // };
        // // maxHeap
        // priority_queue<pair<string, int>, vector<pair<string, int> >, decltype(cmp)> pq(cmp); 
        // for (auto& a : cur->count) {
        //     pq.push(a);
        // }
        // vector<string> res;
        // for (int i = 0; i < 3 && !pq.empty(); ++i) {
        //     res.push_back(pq.top().first);
        //     pq.pop();
        // }
        
        auto cmp = [] (const pair<string, int>& a, const pair<string, int>& b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        };
        // minHeap
        priority_queue<pair<string, int>, vector<pair<string, int> >, decltype(cmp)> pq(cmp);
        for (auto& a : cur->count) {
            pq.push(a);
            if (pq.size() > 3) { // ensure the size of pq is less or equal to 3
                pq.pop();
            }
        }
        vector<string> res(pq.size(), "");
        for (int i = pq.size() - 1; i >= 0; --i) {
            res[i] = pq.top().first;
            pq.pop();
        }
        return res;
    }
private:
    TrieNode* root;
    string prefix;
};

```
