# 0642. Design Search Autocomplete System

https://leetcode.com/problems/design-search-autocomplete-system

## Description

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character `'#'`).

You are given a string array `sentences` and an integer array `times` both of length `n` where `sentences[i]` is a previously typed sentence and `times[i]` is the corresponding number of times the sentence was typed. For each input character except `'#'`, return the top `3` historical hot sentences that have the same prefix as the part of the sentence already typed.

Here are the specific rules:

* The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
* The returned top `3` hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same hot degree, use ASCII-code order (smaller one appears first).
* If less than `3` hot sentences exist, return as many as you can.
* When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

Implement the `AutocompleteSystem` class:

* `AutocompleteSystem(String[] sentences, int[] times)` Initializes the object with the `sentences` and `times` arrays.
* `List<String> input(char c)` This indicates that the user typed the character `c`.
  * Returns an empty array `[]` if `c == '#'` and stores the inputted sentence in the system.
  * Returns the top `3` historical hot sentences that have the same prefix as the part of the sentence already typed. If there are fewer than `3` matches, return them all.

**Example 1:**

```
**Input**
["AutocompleteSystem", "input", "input", "input", "input"]
[[["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]], ["i"], [" "], ["a"], ["#"]]
**Output**
[null, ["i love you", "island", "i love leetcode"], ["i love you", "i love leetcode"], [], []]
**Explanation**
AutocompleteSystem obj = new AutocompleteSystem(["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]);
obj.input("i"); // return ["i love you", "island", "i love leetcode"]. 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.
obj.input(" "); // return ["i love you", "i love leetcode"]. There are only two sentences that have prefix "i ".
obj.input("a"); // return []. There are no sentences that have prefix "i a".
obj.input("#"); // return []. 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.
```

**Constraints:**

* `n == sentences.length`
* `n == times.length`
* `1 <= n <= 100`
* `1 <= sentences[i].length <= 100`
* `1 <= times[i] <= 50`
* `c` is a lowercase English letter, a hash `'#'`, or space `' '`.
* Each tested sentence will be a sequence of characters `c` that end with the character `'#'`.
* Each tested sentence will have a length in the range `[1, 200]`.
* The words in each input sentence are separated by single spaces.
* At most `5000` calls will be made to `input`.

## ac

so ugly. Don't you need to consider the time complexity? whey not just maintain 3 sentence in a trie node. I try to use priorityqueue in each trie node, but just can't update as expected.

```java
class AutocompleteSystem {
    TrieNode root;
    TrieNode r;
    StringBuilder sb; // record input

    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        r = root;
        sb = new StringBuilder();

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

    }

    public List<String> input(char c) {
        List<String> res = new ArrayList<>();

        if (c == '#') { // end input
            String newSentence = sb.toString();
            // update trie and frequency
            build(newSentence, 1);

            r = root; // reset for next input
            sb.setLength(0);
            return res;
        }

        // record input, add when input finish
        sb.append(c);

        if (r == null) return res;
        int pos = c == ' ' ? 0 : c - 'a' + 1;
        r = r.next[pos];
        if (r != null) {
            // get sentences
            PriorityQueue<Map.Entry<String,Integer>> tmp = new PriorityQueue<Map.Entry<String,Integer>>((a, b) -> {
            return a.getValue() != b.getValue() ?  b.getValue() - a.getValue() : a.getKey().compareTo(b.getKey());
        });
            for (Map.Entry<String,Integer> e : r.predict.entrySet()) {
                tmp.offer(e);
            }

            for (int i = 0; i < 3 && !tmp.isEmpty(); i++) {
                Map.Entry<String,Integer> entry = tmp.poll();
                res.add(entry.getKey());
            }
        }

        return res;
    }

    private void build(String s, int time) {
        TrieNode rt = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int pos = c == ' ' ? 0 : c - 'a' + 1;
            if (rt.next[pos] == null) rt.next[pos] = new TrieNode();
            rt = rt.next[pos];
            rt.predict.put(s, rt.predict.getOrDefault(s, 0) + time);
        }
    }
}

class TrieNode {
    TrieNode[] next;
    Map<String, Integer> predict;
    public TrieNode() {
        next = new TrieNode[27]; // frist is " " space
        predict = 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);
 */
```
