JavaScript straightforward with explanations. Two approaches - Trie and First character indexing


  • 2

    First approach - First character indexing

    Since the input size is small, it is sufficient to have improve the brute force solution by just having a separate map of sentences categorized by the first character of each sentence.

    /**
     * @param {string[]} sentences
     * @param {number[]} times
     */
    var AutocompleteSystem = function(sentences, times) {
        this.searchHistory = {};
        'abcdefghijklmnopqrstuvwxyz'.split('').forEach(char => {
            this.searchHistory[char] = {};
        });
        this.inputString = '';
        this.MAX_RESULTS = 3;
        for (let i = 0; i < times.length; i++) {
            const sentence = sentences[i];
            this.searchHistory[sentence[0]][sentence] = times[i];
        }
    };
    
    /**
     * @param {character} c
     * @return {string[]}
     */
    AutocompleteSystem.prototype.input = function(c) {
        if (c === '#') {
            const firstChar = this.inputString[0];
            if (!this.searchHistory[firstChar][this.inputString]) {
                this.searchHistory[firstChar][this.inputString] = 0;
            }
            this.searchHistory[firstChar][this.inputString] += 1;
            this.inputString = '';
            return [];
        }
        this.inputString += c;
        const firstChar = this.inputString[0];
        const results = Object.keys(this.searchHistory[firstChar]).filter(sentence => {
            return sentence.startsWith(this.inputString);
        });
        results.sort((a, b) => {
            const aFreq = this.searchHistory[firstChar][a];
            const bFreq = this.searchHistory[firstChar][b];
            return aFreq !== bFreq ? bFreq - aFreq : (a > b ? 1 : -1);
        });
        return results.slice(0, this.MAX_RESULTS);
    };
    
    /** 
     * Your AutocompleteSystem object will be instantiated and called as such:
     * var obj = Object.create(AutocompleteSystem).createNew(sentences, times)
     * var param_1 = obj.input(c)
     */
    

    Second approach - Augmented Trie

    The Trie used in this solution is modified from my answer in 208 - Implement Trie Prefix Tree to store the count in each last node of the sentence. The code may be long, but it is really quite easy to understand.

    // Using a Trie (Prefix tree).
    /**
     * Initialize your data structure here.
     */
    var Trie = function() {
        this._trie = {};
    };
    
    /**
     * Inserts a string into the trie a number of times.
     * @param {string} word
     * @param {number} [count=1]
     * @return {void}
     */
    Trie.prototype.insert = function(word, count = 1) {
        if (!word.length || count < 1) {
            return;
        }
        let curr = this._trie;
        for (let i = 0; i < word.length; i++) {
            const char = word[i];
            if (!curr.hasOwnProperty(char)) {
                curr[char] = {};
            }
            curr = curr[char];
        }
        if (!curr.hasOwnProperty('#')) {
            curr['#'] = 0;
        }
        curr['#'] += count;
    };
    
    /**
     * Returns if there is any string in the trie that starts with the given prefix.
     * @param {string} prefix
     * @return {Object}
     */
     // Time: O(n), where n is the number of different strings in the Trie.
     // Space: O(1)
    Trie.prototype.stringsStartingWith = function(prefix) {
        if (!prefix.length) {
            return false;
        }
        let curr = this._trie;
        for (let i = 0; i < prefix.length; i++) {
            const char = prefix[i];
            if (!curr.hasOwnProperty(char)) {
                return false;
            }
            curr = curr[char];
        }
        const results = {};
        function traverse(node, chars) {
            if (!node) {
                return;
            }
            Object.keys(node).forEach(char => {
                if (char === '#') {
                    results[chars] = node[char];
                    return;
                }
                traverse(node[char], chars + char);
            });
        }
        traverse(curr, prefix);
        return results;
    };
    
    /**
     * @param {string[]} sentences
     * @param {number[]} times
     */
    var AutocompleteSystem = function(sentences, times) {
        this.trie = new Trie();
        this.inputString = '';
        this.MAX_RESULTS = 3;
        for (let i = 0; i < times.length; i++) {
            const sentence = sentences[i];
            this.trie.insert(sentence, times[i]);
        }
    };
    
    /**
     * @param {character} c
     * @return {string[]}
     */
    AutocompleteSystem.prototype.input = function(c) {
        if (c === '#') {
            this.trie.insert(this.inputString);
            this.inputString = '';
            return [];
        }
        this.inputString += c;
    
        const strings = this.trie.stringsStartingWith(this.inputString);
        const results = Object.keys(strings);
        results.sort((a, b) => {
            const aFreq = strings[a];
            const bFreq = strings[b];
            return aFreq !== bFreq ? bFreq - aFreq : (a > b ? 1 : -1);
        });
        return results.slice(0, this.MAX_RESULTS);
    };
    
    /** 
     * Your AutocompleteSystem object will be instantiated and called as such:
     * var obj = Object.create(AutocompleteSystem).createNew(sentences, times)
     * var param_1 = obj.input(c)
     */
    

Log in to reply
 

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