JavaScript 3-liner using Trie


  • 1

    Sorry for the clickbaity title, this is obviously not possible in just 3 lines of code. But my replaceWords function indeed only contains 3 lines of code.

    I implemented my own Trie class that supports many common operations on strings since LeetCode seems to like to ask Trie questions. For this contest, I added a shortestPrefix method that will traverse the Trie and terminate as soon as it finds that the node is a word.

    const TERMINATING_CHAR = '$$TrieTerminatingCharacter';
    
    class Trie {
        constructor() {
            this._tree = {};
            this.size = 0; // Number of different strings in the Trie. It is not the summation of count.
        }
    
        /**
         * Inserts a string into the Trie, optionally specifying its count.
         * The string's new count will be returned.
         * 0 is returned if the insertion was unsuccessful.
         * @param {string} string
         * @param {number} [count=1]
         * @return {count}
         */
        insert(string, count = 1) {
            if (!string || count < 1) {
                return 0;
            }
            let curr = this._tree;
            for (let i = 0; i < string.length; i++) {
                const char = string[i];
                if (!curr.hasOwnProperty(char)) {
                    curr[char] = {};
                }
                curr = curr[char];
            }
            if (!curr.hasOwnProperty(TERMINATING_CHAR)) {
                this.size++;
                curr[TERMINATING_CHAR] = 0;
            }
            curr[TERMINATING_CHAR] += count;
            return curr[TERMINATING_CHAR];
        }
        
        /**
         * Finds the shortest prefix of a string from words within the Trie.
         * Returns null if there is no prefix of the string within the Trie.
         * @param {string} string
         * @return {string}
         */
        shortestPrefix(string) {
            let curr = this._tree;
            const prefixChars = [];
            
            for (let i = 0; i < string.length; i++) {
                const char = string[i];
                if (curr.hasOwnProperty(TERMINATING_CHAR)) {
                    return prefixChars.join('');
                }
                if (curr.hasOwnProperty(char)) {
                    prefixChars.push(char);
                    curr = curr[char];
                    continue;
                }
                break;
            }
            // If the whole string is a prefix.
            if (curr.hasOwnProperty(TERMINATING_CHAR)) {
                return prefixChars.join('');
            }
            return null;
        }
    }
    
    
    /**
     * @param {string[]} dict
     * @param {string} sentence
     * @return {string}
     */
    var replaceWords = function(dict, sentence) {
        const trie = new Trie();
        dict.forEach(word => trie.insert(word));
        return sentence.split(' ').map(word => trie.shortestPrefix(word) || word).join(' ');
    };
    

Log in to reply
 

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