LeetCode : 642. Design Search Autocomplete System

Trie, PQ
class AutocompleteSystem {
    class Pair {
        String str;
        int cnt;
        Pair(String str, int cnt) {
            this.str = str;
            this.cnt = cnt;
        }
    }
    class Trie {
        Trie[] child = new Trie[128];
        Map<String, Integer> map = new HashMap();

        void insert(String s, int p, int time) {
            if (s.length() == p) return;

            int ind = s.charAt(p);
            if (child[ind] == null) child[ind] = new Trie();

            child[ind].map.merge(s, time, Integer::sum); // merge time
            child[ind].insert(s, p+1, time);
        }

        Trie search(String s, int p) {
            if (s.length() == p) return this;

            int ind = s.charAt(p);
            if (child[ind] != null) return child[ind].search(s, p+1);
            return null;
        }
    }

    Trie root;
    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new Trie(); // !!
        for (int i = 0; i < times.length; i++) root.insert(sentences[i], 0, times[i]);
    }

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

        if (c == '#') {
            root.insert(input, 0, 1); // save to db
            input = "";
            return list;
        }
        else {
            input += c + "";
            Trie t = root.search(input, 0);
            if (t == null) return list;

            Map<String, Integer> map = t.map;

            PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.cnt == b.cnt ? 
                                                         a.str.compareTo(b.str) : b.cnt - a.cnt);

            for (String s : map.keySet()) pq.add(new Pair(s, map.get(s)));

            int top = 3;
            while (!pq.isEmpty() && top-- > 0) {
                Pair p = pq.remove();                    
                list.add(p.str);
            }

            return list;
        }
    }
}

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

LeetCode : 642. Design Search Autocomplete System #479
