Got TLE when submitting the solution, but it passed when I clicked "Run Code".


  • 0

    My code failed when running test case 26: a bunch of 'c's and spaces. But when I run this case separately, it costs 200ms. I thought about storing a map, mapping strings and their frequencies. After all, it is a trade-off between time and space. And for priorityqueue usage, I do not think it is necessary to use that since there are only 3 results you need to return.

    StringBuilder currentInput;
    TrieNode root;
    TrieNode current;
    public AutocompleteSystem(String[] sentences, int[] times) {
        currentInput = new StringBuilder();
        root = new TrieNode();
        current = root;
        buildTrie(sentences, times);
    }
    
    public List<String> input(char c) {
        List<String> ret = new ArrayList<>();
        if (c=='#') {
            insertSentence(currentInput.toString(), 1);
            currentInput = new StringBuilder();
            current = root;
            return new ArrayList<>();
        }
        currentInput.append(c);
        if (current == null) return ret;
        int idx = 0;
        if (c==' ') {
            idx = 26;        
        }
        else{
            idx = c-'a';
        }
        current = current.children[idx];
        if (current == null ) return ret;
        Phrase[] res = new Phrase[3];
        searchTrie(current, res, currentInput);
        for (int i = 0; i<3; i++) {
            if (res[i]!=null) {
                ret.add(res[i].word);
            }
        }
        return ret;
    }
    
    private void searchTrie(TrieNode currentNode, Phrase[] res, StringBuilder currentWord) {
        if (currentNode == null) return;
        if (currentNode.freq > 0) {
            Phrase phrase = new Phrase(currentWord.toString(), currentNode.freq);
            if (res[0] == null || compareSentence(phrase, res[0])) {
                res[2] = res[1];
                res[1] = res[0];
                res[0] = phrase;
            }
            else if (res[1] == null || compareSentence(phrase, res[1])) {
                res[2] = res[1];
                res[1] = phrase;
            }
            else if (res[2] == null || compareSentence(phrase, res[2])) {
                res[2] = phrase;
            }
        }
        for (int i = 0; i<27; i++) {
            StringBuilder next = new StringBuilder(currentWord);
            next.append(i == 26 ?  ' '  : (char)('a' + i));
            searchTrie(currentNode.children[i], res, next); 
        }
    }
    
    private boolean compareSentence(Phrase p1, Phrase p2) {
        if (p1.freq > p2.freq || (p1.freq==p2.freq && p1.word.compareTo(p2.word) <= 0)){
            return true;
        }
        return false;
    }
    
    private void buildTrie(String[] sentences, int[] times) {
        for (int i = 0; i<sentences.length; i++) {
            insertSentence(sentences[i], times[i]);
        }
    }
    
    private void insertSentence(String sentence, int time) {
        TrieNode currentNode = root;
        for (int i = 0; i<sentence.length(); i++) {
            int j = 0;
            if (sentence.charAt(i)==' ')  j = 26;
            else  j = sentence.charAt(i) - 'a';
            if (currentNode.children[j] == null) {
                currentNode.children[j] = new TrieNode();
            }
            currentNode = currentNode.children[j];
            if (i == sentence.length() - 1) {
                currentNode.freq += time;
            }
        }
    }
    
    
    class TrieNode{
        TrieNode[] children;
        int freq;
        public TrieNode () {
            this.children = new TrieNode[27]; // 0 - 25 a-z, 26 space
            this.freq = 0;
        }
    }
    class Phrase{
        String word;
        int freq;
        public Phrase(String word, int freq) {
            this.word = "" + word;
            this.freq = freq;
        }
    }

Log in to reply
 

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