# 0642. Design Search Autocomplete System
###### tags: `Leetcode` `Hard` `Trie` `Design`
Link: https://leetcode.com/problems/design-search-autocomplete-system/description/
## 思路
主要是考察trie
但在trie的基础上 由于我们需要知道每个node都有哪些字符串 以及我们需要知道这个node的所有字符串里面出现频率最高的三个 所以我们给每个TrieNode都加上一个set来存当下node里应该有哪些word

我们可以加一个currnode表示我们现在的位置 新的char来了我们可以接着currnode往下找 只要找一层就行了
这就是为什么我们需要在```add()```首尾都把```curr```设成```root```
加了一个```blank```变量是因为如果搜到某一个点断掉了 也就是返回的ans是空的list 我们就不会往下再搜下一层 也就是保持```curr```不变 这时候我们可以把```blank```设成```true``` 这样只要不换input 都会返回空list
## Code

class AutocompleteSystem {
    class TrieNode{
        TrieNode[] children = new TrieNode[128];
        Set<String> words;
    }

    TrieNode root = new TrieNode();
    TrieNode curr = root;
    Map<String, Integer> count;

    public AutocompleteSystem(String[] sentences, int[] times) {
        int n = sentences.length;
        count = new HashMap<>();
        for(int i=0; i<n; i++){
            count.put(sentences[i], times[i]);
            add(sentences[i]);
        }
    }
    
    private void add(String sentence){
        curr = root;
        for(int i=0; i<sentence.length(); i++){
            char c = sentence.charAt(i);
            if(curr.children[c]==null) curr.children[c] = new TrieNode();
            curr = curr.children[c];
            if(curr.words==null) curr.words = new HashSet<>();
            curr.words.add(sentence);
        }
        curr = root;
    }

    boolean blank = false;
    StringBuilder input = new StringBuilder();
    public List<String> input(char c) {
        List<String> ans = new ArrayList<>();
        if(c=='#'){
            curr = root;
            blank = false;
            String s = input.toString();
            add(s);
            count.put(s, count.getOrDefault(s,0)+1);
            input.setLength(0);
            return ans;
        }
        input.append(c);
        if(blank) return ans;
        if(curr.children[c]==null){
            blank = true;
            return ans;
        }
        else{
            curr = curr.children[c];
            Queue<String> pq = new PriorityQueue<>((a,b)->(count.get(b)==count.get(a)?(b.compareTo(a)):(count.get(a)-count.get(b))));
            for(String s:curr.words){
                pq.add(s);
                if(pq.size()>3) pq.poll();
            }
            while(!pq.isEmpty()){
                ans.add(0, pq.poll());
            }
        }
        return ans;
    }
}