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

**Example:**\
**Operation:**&#x41;utocompleteSystem(\["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:**&#x69;nput('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:**&#x69;nput(' ')\
**Output:**\["i love you","i love leetcode"]\
**Explanation:**\
There are only two sentences that have prefix`"i "`.

**Operation:**&#x69;nput('a')\
**Output:**\[]\
**Explanation:**\
There are no sentences that have prefix`"i a"`.

**Operation:**&#x69;nput('#')\
**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.

**Thoughts:**

1. Each node records: next (children), counts(String that current tries represents so far -> frequency count)
2. Only thing more than a normal `Trie`is added a map of `sentence`to `count`in each of the `Trie`node to facilitate process of getting top 3 results.

**Code: T:O(l \* mlogm) for each time, assume current input word is l, there are m keys in the node of cur.**

**S: O(max(l)^2 \* # of inputs)**

```java
class AutocompleteSystem {
    TrieNode root;
    String prefix;

    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        prefix = "";
        for (int i = 0; i < times.length; i++){
            add(sentences[i], times[i]);
        }
    }

    public List<String> input(char c) {
        // termination
        if(c == '#'){
            add(prefix, 1);
            prefix = "";
            return new ArrayList<String>();
        }

        prefix += c;
        TrieNode cur = root;
        for(char cc : prefix.toCharArray()){
            TrieNode next = cur.next.get(cc);
            if(next == null)
                return new ArrayList<String>();
            cur = next;
        }

        // Pull out + sort all the counting infor for current string prefix
        PriorityQueue<Pair> pq = new PriorityQueue<>((a,b) -> a.c == b.c? a.s.compareTo(b.s): b.c - a.c);
        // Add all elements into queue
        for(String s: cur.counts.keySet())
            pq.add(new Pair(s, cur.counts.get(s)));

        List<String> res = new ArrayList<>();
        // add top 3 results
        for(int i = 0; i < 3 && !pq.isEmpty(); i++)
            res.add(pq.poll().s);

        return res;
    }

    private void add(String s, int count){
        TrieNode cur = root;
        for(char c: s.toCharArray()){
            TrieNode next = cur.next.get(c);
            if(next == null){
                next = new TrieNode();
                cur.next.put(c, next);
            }
            cur = next;
            cur.counts.put(s, cur.counts.getOrDefault(s,0) + count); // First go then add is to to avoid putting in root
        }
    }


    class Pair {
        String s;
        int c;
        public Pair(String s, int count){
            this.s = s;
            this.c = count;
        }
    }

   class TrieNode{
        Map<Character,TrieNode> next;
        Map<String, Integer> counts;
        public TrieNode(){
            next = new HashMap<>();
            counts = new HashMap<>();
        }
    }
}

/**
 * Your AutocompleteSystem object will be instantiated and called as such:
 * AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
 * List<String> param_1 = obj.input(c);
 */
```