AC 95% Javascript Solution


  • 0
    S
    1. Create a TriNode class, with next which contains next char, and word, which is the end of the word.

    2. Create a Trie class, with one root TriNode.

    3. Upon Insert, we check through each TriNode through next, if the next node is undefined, we create a new node, and assign word to the leaf node.

    4. Upon Search, we check through each node through next, just like Insert. However when we don't see a next node, we return false; until the leaf node, we check if word was assigned or null.

    5. Similar to Search, startsWith has the same logic, until the last part, we don't check if the node contains the prefix or not --- we don't care.

    Note: 'a'.charCodeAt(0) === 97, which I don't really assign to a variable in the code.

    /**
     * Initialize your data structure here.
     */
    var Trie = function() {
        this.root = new TriNode();
    };
    
    var TriNode = function () {
        this.next = new Array(26);
        this.word = null;
    }
    /**
     * Inserts a word into the trie. 
     * @param {string} word
     * @return {void}
     */
    Trie.prototype.insert = function(word) {
        let curr = this.root;
        for (let i = 0; i < word.length; i++) {
            if (!curr.next[word[i].charCodeAt(0) - 97]) {
                curr.next[word[i].charCodeAt(0) - 97] = new TriNode();
            }
            curr = curr.next[word[i].charCodeAt(0) - 97];
        }
        curr.word = word;
    };
    
    /**
     * Returns if the word is in the trie. 
     * @param {string} word
     * @return {boolean}
     */
    Trie.prototype.search = function(word) {
        let curr = this.root;
        for (let i = 0; i < word.length; i++) {
            if (!curr.next[word[i].charCodeAt(0) - 97]) return false;
            curr = curr.next[word[i].charCodeAt(0) - 97];
        }
        if (curr.word === word) return true;
        return false;
    };
    
    /**
     * Returns if there is any word in the trie that starts with the given prefix. 
     * @param {string} prefix
     * @return {boolean}
     */
    Trie.prototype.startsWith = function(prefix) {
        let curr = this.root;
        for (let i = 0; i < prefix.length; i++) {
            if (!curr.next[prefix[i].charCodeAt(0) - 97]) return false;
            curr = curr.next[prefix[i].charCodeAt(0) - 97];
        }
        return true;
    };
    
    /** 
     * Your Trie object will be instantiated and called as such:
     * var obj = Object.create(Trie).createNew()
     * obj.insert(word)
     * var param_2 = obj.search(word)
     * var param_3 = obj.startsWith(prefix)
     */
    

Log in to reply
 

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