Java solution with comments, using radix tree and priority queue


  • 0
    C
    public class AutocompleteSystem {
        
        private Node root; //root of the trie
        
        private Node curr; //current node of the trie
        
        //The character will only be lower-case letters ('a' to 'z'), blank space (' ') or a special character ('#').
        //build a radix tree with node storing times, or use another HashMap to store sentence->times
        public AutocompleteSystem(String[] sentences, int[] times) {
            root = new Node("");
            for (int i = 0; i < sentences.length; ++i) {
                curr = root;
                for (int j = 0; j < sentences[i].length(); ++j) {
                    char ch = sentences[i].charAt(j);
                    int k = 0;
                    if (ch == ' ') {
                        k = 26;
                    }
                    else {
                        k = ch - 'a';
                    }
                    if (curr.children[k] == null) {
                        curr.children[k] = new Node(curr.prefix+ch);
                    }
                    curr = curr.children[k];
                }
                curr.count = times[i];
            }
            curr = root; //reset for input
        }
        
        //find all existing sentences with the prefix
        // use priority queue or SortedSet to maintain the largest 3 sentence with prefix
        //remember the typed charaters and radix node, if backspace is allowed, use parent node
        //when type '#' add the stored characters into the radix tree if exists, otherwise increment the time.
        public List<String> input(char c) {
            if (c == '#') { //complete the current sentence
                curr.count += 1;
                curr = root;
                return Collections.emptyList();
            }
            int k = c == ' ' ? 26 : c-'a';
            if (curr.children[k] == null) {
                curr.children[k] = new Node(curr.prefix+c);
            }
            curr = curr.children[k];
            return top3(curr);
        }
        
        private List<String> top3(Node curr) {
            PriorityQueue<Node> queue = new PriorityQueue<>(
                (a, b) -> {
                    if (b.count != a.count) {
                        return b.count - a.count;
                    }
                    return a.prefix.compareTo(b.prefix);
                });
            dfs(curr, queue);
            List<String> result = new ArrayList<>(3);
            for (int i = 0; i < 3; ++i) {
                if (queue.peek() == null) {
                    break;
                }
                result.add(queue.poll().prefix);
            }
            return result;
        }
        
        private void dfs(Node curr, PriorityQueue<Node> queue) {
            if (curr.count > 0) {
                queue.offer(curr);
            }
            for (int i = 0; i < curr.children.length; ++i) {
                if (curr.children[i] != null) {
                    dfs(curr.children[i], queue);
                }
            }
        }
        
        public static class Node {
            int count; //count of prefix
            String prefix; //prefix from root to it
            Node[] children; 
            Node(String prefix) {
                this.count = 0;
                this.children = new Node[27]; //a-z and space
                this.prefix = prefix;
            }
        }
    }
    

Log in to reply
 

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