# Design Search Autocomplete System

`Design`

**Hard**

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.

## Solution & Analysis

### Trie + PriorityQueue (Min-Heap)

249 ms, faster than 76.43%

```java
class AutocompleteSystem {

    class TrieNode {
        Map<Character, TrieNode> children; 
        Map<String, Integer> counts;
        boolean isWord;

        public TrieNode () {
            children = new HashMap<>();
            counts = new HashMap<>();
            isWord = false;
        }
    }

    TrieNode root;
    String prefix;

    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        prefix = "";

        for (int i = 0; i < sentences.length; i++) {
            add(sentences[i], times[i]);
        }
    }

    private void add(String s, int count) {
        TrieNode curr = root;
        for (char c: s.toCharArray()) {
            curr.children.putIfAbsent(c, new TrieNode());
            curr = curr.children.get(c);
            curr.counts.put(s, curr.counts.getOrDefault(s, 0) + count);
        }
        curr.isWord = true;
    }

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

        TrieNode curr = root;

        for (char ch: prefix.toCharArray()) {
            if (!curr.children.containsKey(ch)) {
                return new ArrayList<String>();
            }
            curr = curr.children.get(ch);
        }

        Comparator<Map.Entry<String, Integer>> cmp = new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> a, Map.Entry<String, Integer> b) {
                return a.getValue() == b.getValue() ? b.getKey().compareTo(a.getKey()) : a.getValue() - b.getValue();
            }
        };
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(cmp);
        int k = 3; 
        for (Map.Entry<String, Integer> entry: curr.counts.entrySet()) {
            pq.offer(entry);
            while (!pq.isEmpty() && pq.size() > k) {
                pq.poll();
            }
        }

        ArrayList<String> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(0, pq.poll().getKey());
        }
        return res;
    }
}

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

### Trie + PriorityQueue (Max-Heap)

```java
class AutocompleteSystem {
    class TrieNode {
        Map<Character, TrieNode> next;
        Map<String, Integer> count;
        boolean isWord;

        public TrieNode() {
            next = new HashMap<>();
            count = new HashMap<>();
            isWord = false;
        }
     }

    TrieNode root;
    String prefix;

    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        prefix = "";

        for (int i = 0; i < sentences.length; i++) {
            add(sentences[i], times[i]);
        }
    }

    private void add(String str, int count) {
        char[] chas = str.toCharArray();
        TrieNode node = root;

        for (char c: chas) {
            TrieNode nextNode = node.next.get(c);
            if (nextNode == null) {
                nextNode = new TrieNode();
                node.next.put(c, nextNode);
            }
            node = nextNode;
            node.count.put(str, node.count.getOrDefault(str, 0) + count);
        }

        node.isWord = true;
    }

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

        prefix = prefix + c;
        // System.out.println(prefix);
        TrieNode node = root;
        for (char cc: prefix.toCharArray()) {
            node = node.next.get(cc);
            if (node == null) return new ArrayList<>();
        }

        PriorityQueue<Pair> pq = new PriorityQueue<>((o1, o2) -> (o1.count == o2.count ? o1.str.compareTo(o2.str) : o2.count - o1.count));

        for (String str: node.count.keySet()) {
            pq.add(new Pair(str, node.count.get(str)));
        }

        List<String> res = new ArrayList<>();
        for (int i = 0; i < 3 && !pq.isEmpty(); i++) {
            Pair pair = pq.poll();
            // System.out.println(pair.str + " " + pair.count);
            res.add(pair.str);
        }

        return res;
    }

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

}
```

### LeetCode Official

Trie + List

```java
public class AutocompleteSystem {
    class Node {
        Node(String st, int t) {
            sentence = st;
            times = t;
        }
        String sentence;
        int times;
    }
    class Trie {
        int times;
        Trie[] branches = new Trie[27];
    }
    public int int_(char c) {
        return c == ' ' ? 26 : c - 'a';
    }
    public void insert(Trie t, String s, int times) {
        for (int i = 0; i < s.length(); i++) {
            if (t.branches[int_(s.charAt(i))] == null)
                t.branches[int_(s.charAt(i))] = new Trie();
            t = t.branches[int_(s.charAt(i))];
        }
        t.times += times;
    }
    public List < Node > lookup(Trie t, String s) {
        List < Node > list = new ArrayList < > ();
        for (int i = 0; i < s.length(); i++) {
            if (t.branches[int_(s.charAt(i))] == null)
                return new ArrayList < Node > ();
            t = t.branches[int_(s.charAt(i))];
        }
        traverse(s, t, list);
        return list;
    }
    public void traverse(String s, Trie t, List < Node > list) {
        if (t.times > 0)
            list.add(new Node(s, t.times));
        for (char i = 'a'; i <= 'z'; i++) {
            if (t.branches[i - 'a'] != null)
                traverse(s + i, t.branches[i - 'a'], list);
        }
        if (t.branches[26] != null)
            traverse(s + ' ', t.branches[26], list);
    }
    Trie root;
    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new Trie();
        for (int i = 0; i < sentences.length; i++) {
            insert(root, sentences[i], times[i]);
        }
    }
    String cur_sent = "";
    public List < String > input(char c) {
        List < String > res = new ArrayList < > ();
        if (c == '#') { 
            insert(root, cur_sent, 1);
            cur_sent = "";
        } else {
            cur_sent += c;
            List < Node > list = lookup(root, cur_sent);
            Collections.sort(list, (a, b) -> a.times == b.times ? a.sentence.compareTo(b.sentence) : b.times - a.times);
            for (int i = 0; i < Math.min(3, list.size()); i++)
                res.add(list.get(i).sentence);
        }
        return res;
    }
}
```