Solution to "Design Search Autocomplete System" on Leetcode

AutocompleteSystem.java

class AutocompleteSystem {

    TrieNode root;
    TrieNode rootCopy;
    StringBuilder currSentence;
    Map<String, Sentence> sentenceRefs;
    
    /**
     * Requirements:
     * - Users may input a sentence (each sentence must contain at least one word and end with "#")
     * - For each character typed (except the "#"), I need to return the top 3 historical "hot" sentences with the same
     * prefix as part of the sentence already typed
     * - Hot degree of a sentence: no times the exact sentence has been typed before
     * - The returned top 3 sentences should be sorted by hot degree. If several sentences have the same hot degree,
     * you need to use the ASCII-order
     * - If less than 3 sentences exist, then return as many as you can
     * - When the input is a special character, it means the sentence ends, so return an empty list
     * <p>
     * Approach:
     * - First of all, we need to remember that it is possible to see a sentence again in the future, so we need
     * to be able to update the number of times we've seen it easily. For this reason, we create a map
     * Map<String, Sentence> so that we can store a mapping of each sentence to its sentence object (see class Sentence)
     * this way, if we find a sentence we've seen before, all we need to do is increment the times field on this
     * reference and all the TrieNodes that have the instance will be updated as  well.
     * - Build a Trie. For each sentence, each TrieNode should contain a list of all the sentences that have the prefix
     * up to that point. We can get this references from the map we created earlier.
     * - For the `input` method, we must remember that every entry forms a sentence until the # character. So we must
     * handle a few things here:
     * - Store all characters we've seen before the # char in a StringBuilder
     * - I used `rootCopy` because for each sentence we don't want to search from the root, we want to search
     * from the level the last character in the string stopped at. `rootCopy` achieves that
     * - for each char that is valid, we add it to our string builder storing our sentences
     * - for each char that is valid, we keep searching our rootCopy context and returning the
     * top Math.min(3, sentences on the rootCopy node count)
     * - Whenever rootCopy == null, we must remember that we can't search for that sentence again. It is null.
     * So if rootCopy is ever null, we must keep returning an empty list until we start another sentence and
     * refresh rootCopy (i.e. rootCopy = root)
     * - When we get the '#' char, it means our sentence has ended and we must insert into our Trie (incase
     * someone searchs for it in the future)
     * - While inserting:
     * - We check if it in Map<String, Sentence> map
     * - If it's not there, we have never seen the sentence before, so:
     * ~ we insert it into the map with a sentence object with times = 1
     * ~ we insert it into the trie and on each trie node, we add the sentence ref from the map to
     * List<Sentence>
     * - If it's there, all  we have to  do is increment the times we've seen and this  will update  all the
     * Sentence references
     */
    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        rootCopy = root;
        currSentence = new StringBuilder();
        sentenceRefs = new HashMap<>();
        createSentenceReferences(sentences, times);
        buildTrie(sentences);
    }

    private void buildTrie(String[] sentences) {
        for (String curr : sentences) {
            insertSentenceIntoTrie(curr);
        }
    }

    private void insertSentenceIntoTrie(String curr) {
        TrieNode node = root;
        for (char c : curr.toCharArray()) {
            if (node.next[c] == null) {
                node.next[c] = new TrieNode(c);
            }
            node.next[c].sentences.add(sentenceRefs.get(curr));
            node = node.next[c];
        }
    }

    private void createSentenceReferences(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; i++) {
            Sentence curr = new Sentence(sentences[i], times[i]);
            sentenceRefs.put(sentences[i], curr);
        }
    }

    public List<String> input(char c) {

        if (c == '#') {
            System.out.println(currSentence.toString());
            rootCopy = root;
            insertUserInputIntoTrie();
            currSentence = new StringBuilder();
            return new ArrayList<>();
        }
        
        currSentence.append(c);
        if(rootCopy == null){
            return new ArrayList<>();
        }
        
        List<String> result = new ArrayList<>();
        if (rootCopy.next[c] != null) {
            List<Sentence> sentenceList = rootCopy.next[c].sentences;
            sentenceList.sort((o1, o2) -> {
                int compare = o2.times - o1.times;
                return compare == 0 ? o1.sentence.compareTo(o2.sentence) : compare;
            });

            int maxLen = Math.min(sentenceList.size(), 3);
            for (int i = 0; i < maxLen; i++) {
                result.add(sentenceList.get(i).sentence);
            }

            rootCopy = rootCopy.next[c];            
        } else {
            rootCopy = null;
        }
        
        
        return result;
    }

    private void insertUserInputIntoTrie() {
        String newSentence = currSentence.toString();
        if (sentenceRefs.containsKey(newSentence)) {
            sentenceRefs.get(newSentence).times++;
            return;
        }

        sentenceRefs.put(newSentence, new Sentence(newSentence, 1));
        insertSentenceIntoTrie(newSentence);
    }
}

class Sentence {
    String sentence;
    int times;

    Sentence(String sentence, int times) {
        this.sentence = sentence;
        this.times = times;
    }
}

class TrieNode {
    char c;
    TrieNode[] next;
    List<Sentence> sentences;

    TrieNode() {
        next = new TrieNode[128];
        sentences = new ArrayList<>();
    }

    TrieNode(char c) {
        this.c = c;
        next = new TrieNode[128];
        sentences = new ArrayList<>();
    }
}
/**
 * Your AutocompleteSystem object will be instantiated and called as such:
 * AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
 * List<String> param_1 = obj.input(c);
 */