My Javascript Trie Solution


  • 0
    S
    /**
     * @constructor
     * Initialize your data structure here.
     */
    var TrieNode = function() {
        this.val = null;
        this.children = [];
        this.string = "";
    };
    
    var Trie = function() {
        this.root = new TrieNode();
    };
    
    /**
     * @param {string} word
     * @return {void}
     * Inserts a word into the trie.
     */
    Trie.prototype.insert = function(word) {
        var current = this.root;
        for(var i = 0; i < word.length; i++){
            if(current.getChild(word.charCodeAt(i) - 'a'.charCodeAt(0)) !== undefined){
                current = current.getChild(word.charCodeAt(i) - 'a'.charCodeAt(0));
            }else {
                //if it doesn't have this current char
                //push it into the children of current node
                var additional = new TrieNode();
                current.children[word.charCodeAt(i) - 'a'.charCodeAt(0)] = additional;
                current = additional;
                 
            }
            
        }
        current.string = word;
    };
    
    TrieNode.prototype.getChild = function(index){
        if(index < 0 || index > 26) return null;
        return this.children[index];
    };
    /**
     * @param {string} word
     * @return {boolean}
     * Returns if the word is in the trie.
     */
    Trie.prototype.search = function(word) {
        var current = this.root;
        for(var i = 0; i < word.length; i++){
            if(current.getChild(word.charCodeAt(i) - 'a'.charCodeAt(0)) !== undefined){
                current = current.getChild(word.charCodeAt(i) - 'a'.charCodeAt(0));
            }else {
                return false;
            }
            
        }
        return current.string === word;
    };
    
    /**
     * @param {string} prefix
     * @return {boolean}
     * Returns if there is any word in the trie
     * that starts with the given prefix.
     */
    Trie.prototype.startsWith = function(prefix) {
        var current = this.root;
        for(var i = 0; i < prefix.length; i++){
            if(current.getChild(prefix.charCodeAt(i) - 'a'.charCodeAt(0)) !== undefined){
                current = current.getChild(prefix.charCodeAt(i) - 'a'.charCodeAt(0));
            }else {
                return false;
            }
        }
        return true;
    };
    
    /**
     * Your Trie object will be instantiated and called as such:
     * var trie = new Trie();
     * trie.insert("somestring");
     * trie.search("key");
     */

Log in to reply
 

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