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)
*/
《Trie 的简易版 js 实现》有2个想法
评论已关闭。