实现字典树

[TieMuZhen]

LeetCode 208

var Node = function() {
    this.value = null;
    this.isFinished = false;
    this.children = new Array(26);
}
var Trie = function() {
    this.root = new Node();
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let cur = this.root;
    for(let i = 0; i < word.length; i++){
        let index = word[i].charCodeAt() - "a".charCodeAt();
        if(cur.children[index] == null){
            cur.children[index] = new Node(); 
        }
        cur = cur.children[index];
        cur.value = word[i];
        if(i == word.length - 1){
            cur.isFinished = true;
        }
    }
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let cur = this.root;
    for(let i = 0; i < word.length; i++){
        let index = word[i].charCodeAt() - 'a'.charCodeAt();
        if(cur.children[index] == null){
            return false;
        }else{
            cur = cur.children[index];
            if(i == word.length - 1 && cur.isFinished){
                return true;
            }
        }
    }
    return false;
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let cur = this.root;
    for(let i = 0; i < prefix.length; i++){
        let index = prefix[i].charCodeAt() - 'a'.charCodeAt();
        if(cur.children[index]){
            cur = cur.children[index];
        }else{
            return false;
        }
        if(i == prefix.length - 1){
            return true;
        }
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */