Trie 的简易版 js 实现

Trie 能解决什么问题？

假设我们有一个数组：['tiger', 'monkey', 'elephant', 'dog']，我们想要查找里面有没有 dog，最简单的方法是遍历数组，如果要查 10000 次，则遍历数组的次数是 1w * 4 = 4w；如果我们用 trie 来解决这个问题，则会大大的提升我们的速度。构建 trie 的遍历次数是 5 + 6 + 7 + 3 = 21，再查询 10000 次，则是 10000 * 3 + 21 = 30021。很明显，查询次数越多，trie 的性能优势就越明显。

上面的计算可能并不专业，仅供参考。

看看具体的实现代码

/**
 * Initialize your data structure here.
 */
var Trie = function() {
    this.root = {
        isWord: false,
        next: new Map()
    }
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let cur = this.root
    for(let c of word) {
        if(!cur.next.has(c))
            cur.next.set(c, { isWord: false, next: new Map() })
        cur = cur.next.get(c)
    }
    cur.isWord = true
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let cur = this.root
    for(let c of word) {
        if(!cur.next.has(c))
            return false
        cur = cur.next.get(c)
    }
    return cur.isWord
};

/**
 * 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 cur = this.root
    for(let c of prefix) {
        if(!cur.next.has(c))
            return false
        cur = cur.next.get(c)
    }
    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)
 */