Java Straightforward Trie Solution


  • 0
    H
    public class AutocompleteSystem {
        class Node{
            Node[] next;
            Map<String, Integer> map;
            Node(){
                next = new Node[27];
                map = new HashMap<>();
            }
        }
        Node root = new Node();
        StringBuilder sb = new StringBuilder();
        private void put(String s){
            char[] c = s.toCharArray();
            Node cur = root;
            for(int i = 0; i < c.length; i++){
                int ch = trans(c[i]);
                if(cur.next[ch] == null)
                    cur.next[ch] = new Node();
                cur = cur.next[ch];
                cur.map.put(s, cur.map.getOrDefault(s, 0) + 1);
            }
        }
        
        private Map<String, Integer> get(String s){
            char[] c = s.toCharArray();
            Node cur = root;
            for(int i = 0; i < c.length; i++){
                int ch = trans(c[i]);
                if(cur.next[ch] == null)
                    return null;
                cur = cur.next[ch];
                if(i == c.length-1)
                    return cur.map;
            }
            return null;
        }
        
        private int trans(char ch){
            return ch == ' ' ? 26 : ch - 'a';
        }
        public AutocompleteSystem(String[] sentences, int[] times) {
            for(int i = 0; i < sentences.length; i++){
                String s = sentences[i];
                for(int j = 0; j < times[i]; j++){
                    put(s);
                }
            }
        }
        
        public List<String> input(char c) {
            if(c != '#'){
                sb.append(c);
                Map<String, Integer> map = get(sb.toString());
                if(map == null)
                    return new ArrayList<>();
                List<Map.Entry<String, Integer>> tmp = new ArrayList<>();
                for(Map.Entry<String, Integer> entry : map.entrySet()){
                    tmp.add(entry);
                }
                Collections.sort(tmp, new Comparator<Map.Entry<String, Integer>>(){
                    public int compare(Map.Entry<String, Integer> A, Map.Entry<String, Integer> B){
                        if(A.getValue() != B.getValue())
                            return B.getValue() - A.getValue();
                        else
                            return A.getKey().compareTo(B.getKey());
                    }
                });
                
                List<String> res = new ArrayList<>();
                for(int i = 0; i < 3 && i < tmp.size(); i++)
                    res.add(tmp.get(i).getKey());
                return res;
            }
            else{
                put(sb.toString());
                sb = new StringBuilder();
                return new ArrayList<>();
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.