Java Trie Solution


  • 0
    G

    Because we only need to return the top 3 sentences for each input, the TrieNode can maintain a size 3 rank list.

    public class AutocompleteSystem {
        private Map<String, Integer> map;
        private TrieNode root;
        private String currentInput;
        private TrieNode currentNode;
    
        class TrieNode {
            TrieNode[] children;
            List<String> rank;
    
            TrieNode() {
                children = new TrieNode[256];
                rank = new ArrayList<>();
            }
        }
    
        public AutocompleteSystem(String[] sentences, int[] times) {
            map = new HashMap<>();
            root = new TrieNode();
            currentNode = root;
            currentInput = "";
            for (int i = 0; i < sentences.length; i++) {
                insertSentence(sentences[i], times[i]);
            }
        }
    
        private void insertSentence(String sentence, int times) {
            if (sentence == "") return;
            map.put(sentence, times);
            insertSentenceToTrie(sentence, 0, root, times);
        }
    
        private void insertSentenceToTrie(String sentence, int index, TrieNode root, int times) {
            if (index >= sentence.length()) return;
            char cur = sentence.charAt(index);
            if (root.children[cur] == null) root.children[cur] = new TrieNode();
            updateRank(root.children[cur], sentence, times);
            insertSentenceToTrie(sentence, index + 1, root.children[cur], times);
        }
    
        private void updateRank(TrieNode node, String sentence, int times) {
            boolean alreadyIn = false;
            for (int i = 0; i < node.rank.size(); i++) {
                if (node.rank.get(i).equals(sentence)) {
                    alreadyIn = true;
                    break;
                }
            }
    
            if (!alreadyIn) {
                node.rank.add(sentence);
            }
    
            Collections.sort(node.rank, (s1, s2) -> {
                int times1 = map.get(s1);
                int times2 = map.get(s2);
                if (times1 == times2) {
                    int len = Math.min(s1.length(), s2.length());
                    for (int i = 0; i < len; i++) {
                        if (s1.charAt(i) != s2.charAt(i)) return s1.charAt(i) - s2.charAt(i);
                    }
    
                    return s1.length() - s2.length();
                }
    
                return times2 - times1;
            });
            if (node.rank.size() > 3) {
                node.rank = node.rank.subList(0, 3);
            }
        }
        
        public List<String> input(char c) {
            List<String> list = new ArrayList<>();
            if (c == '#') {
                int times = map.containsKey(currentInput) ? map.get(currentInput) + 1 : 1;
                insertSentence(currentInput, times);
                currentInput = "";
                currentNode = root;
                return list;
            }
    
            return search(c);
        }
    
        private List<String> search(char c) {
            currentInput += c;
            if (currentNode == null) return new ArrayList<>();
            currentNode = currentNode.children[c];
            if (currentNode == null) return new ArrayList<>();
            return currentNode.rank;
        }
    }
    

Log in to reply
 

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