208. 实现 Trie (前缀树).md

思路

用map实现树的查找

代码

/**
 * Initialize your data structure here.
 */
var Trie = function() {
    this.cache = {}
};

Trie.prototype.insert = function(word) {
    let hash = this.cache
    for(let i of word) {
        !hash[i] && (hash[i] = {});
        hash = hash[i]
    }
    hash.finish = 1;
};

Trie.prototype.find = function(word) {
    let hash = this.cache
    for(let i of word) {
        if (!hash[i]) return false;
        hash = hash[i]
    }
    return hash
}

Trie.prototype.search = function(word) {
    let hash = this.find(word)
    return hash && hash.finish !== undefined
};

Trie.prototype.startsWith = function(prefix) {
    return this.find(prefix) !== false;
};

复杂度分析

时间复杂度 $O(N)$

空间复杂度 $O(N)$