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

思路：这题跟 Search Suggestion System一模一样，细微的差别是input type完了之后，输入的那个词，也要进入词频统计，那么trienode里面需要存sentence的frequency，另外注意的地方是：type的时候，如果是null了，那么以后的cur也是null，

class AutocompleteSystem {
    public class TrieNode {
        public HashMap<Character, TrieNode> nodemap; // 因为有空格；所以用hashmap，这样也节约空间；
        public boolean isword;
        public String word;
        public HashMap<String, Integer> fremap;
        public TrieNode() {
            this.nodemap = new HashMap<>();
            this.isword = false;
            this.word = null;
            this.fremap = new HashMap<>();
        }
    }
    
    public class Trie {
        public TrieNode root;
        public Trie() {
            this.root = new TrieNode();
        }
        
        public void insert(String word, int time) {
            TrieNode cur = root;
            for(int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if(cur.nodemap.get(c) == null) {
                    cur.nodemap.put(c, new TrieNode());
                }
                cur = cur.nodemap.get(c);
                // 一定是沿途的trieNode都要记录，而不是最后才记录；
                cur.fremap.put(word, cur.fremap.getOrDefault(word, 0) + time);
            }
            cur.isword = true;
            cur.word = word;
        }
    }

    private Trie trie;
    private StringBuilder sb;
    private TrieNode cur;
    private class Node {
        public String word;
        public int fre;
        public Node(String word, int fre) {
            this.word = word;
            this.fre = fre;
        }
    }
    
    public AutocompleteSystem(String[] sentences, int[] times) {
        this.trie = new Trie();
        this.sb = new StringBuilder();
        this.cur = trie.root;
        for(int i = 0; i < sentences.length; i++) {
            trie.insert(sentences[i], times[i]);
        }
    }
    
    public List<String> input(char c) {
        List<String> res = new ArrayList<>();
        if(c == '#') {
            // last char;
            String lastword = sb.toString();
            trie.insert(lastword, 1);
            cur = trie.root;
            sb = new StringBuilder();
        } else {
            sb.append(c);
            if(cur != null && cur.nodemap.get(c) != null) {
                cur = cur.nodemap.get(c);
                List<Node> nodelist = new ArrayList<Node>();
                for(String key: cur.fremap.keySet()) {
                    Node node = new Node(key, cur.fremap.get(key));
                    nodelist.add(node);
                }
                
                Collections.sort(nodelist, (a, b) -> (a.fre != b.fre ? b.fre - a.fre : a.word.compareTo(b.word)));
                for(int i = 0; i < Math.min(3, nodelist.size()); i++) {
                    res.add(nodelist.get(i).word);
                }
                
            } else {
                cur = null;
            }
        }
        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);
 */