Trie Solution with O(len(input string)) lookup time complexity without the need of traversal&ordering


  • 0
    Q

    The idea is to use an array to store the top 3 results for each node so we don't need to traverse all the Nodes in the subtree and sort them to get the top 3 results. Time complexity decreases from O(nC) to O(C) where n is the total number of sentences in the Trie and C is the length of the input string.

    class TrieNode {
        TrieNode[] children;
        boolean isWord;
        String word;
        int cnt;
        TrieNode[] t; //use to store top 3 results in the subtrees
        public TrieNode() {
            children = new TrieNode[128];
            isWord  = false;
            word = "";
            cnt = 0;
            t = new TrieNode[3];
        } 
    }
    
    class Trie {
        TrieNode root;
        String in;
        
        public Trie() {
            root = new TrieNode();
            in = "";
        }
        
        List<String> lookup() {
            TrieNode p = root;
            for(int i = 0; i < in.length(); i++) {
                char c = in.charAt(i);
                if(p.children[c] == null) return Collections.emptyList();
                p = p.children[c];
            }
            List<String> result = new ArrayList<>();
            for(TrieNode pt : p.t) {
                if(pt != null) result.add(pt.word);
            }
            return result;
        }
        
        void insert(String s, int time) {
            TrieNode p = root;
            for(int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if(p.children[c] == null) p.children[c] = new TrieNode();
                p = p.children[c];
            }
            p.isWord = true;
            p.word = s;
            p.cnt += time; 
            TrieNode np = root;
            for(int i = 0; i < s.length(); i++) { //update max-result array for each ancestor node of the newly inserted node p
                setMax(np, p);
                char c = s.charAt(i);
                np = np.children[c];
            }
            setMax(np, p);
        }
        
       
        void setMax(TrieNode np, TrieNode p) {
            for(int i = 0; i < 3; i++) {
                if(np.t[i] == p) {
                    sortMax(np.t);
                    return;
                }
            }
            
            for(int i = 0; i < 3; i++) {
                if(np.t[i] == null) {
                    np.t[i] = p;        
                    sortMax(np.t);
                    return;
                }
            }
            TrieNode[] tmp = new TrieNode[4];
            for(int i = 0; i < 3; i++) tmp[i] = np.t[i];
            tmp[3] = p;
            sortMax(tmp);
            for(int i = 0; i < 3; i++) np.t[i] = tmp[i];
        }
        void sortMax(TrieNode[] t) {
            List<TrieNode> tmp = new ArrayList<>();
            for(TrieNode tp : t) {
                if(tp != null) tmp.add(tp);
            }
            Collections.sort(tmp, new Comparator<TrieNode>() {
                @Override
                public int compare(TrieNode t1, TrieNode t2) {
                    if(t1.cnt != t2.cnt) return t2.cnt - t1.cnt;
                    else return t1.word.compareTo(t2.word);
                }
            });
            for(int i = 0; i < tmp.size(); i++) t[i] = tmp.get(i);
            for(int i = tmp.size(); i < t.length; i++) t[i] = null;
        }
    }
    
    public class AutocompleteSystem {
        Trie t;
        public AutocompleteSystem(String[] sentences, int[] times) {
            t = new Trie();
            for(int i = 0; i < sentences.length; i++) {
                t.insert(sentences[i], times[i]);
            }
        }
        
        public List<String> input(char c) {
            if(c == '#') {
                t.insert(t.in, 1);
                t.in = "";
                return Collections.emptyList();
            }
            else {
                t.in += c;
                return t.lookup();
            }
        }
    }
    

Log in to reply
 

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