LeetCode208 實作 Trie 字首樹

• 題目
• 解題

題目

解題

對字首樹資料結構沒有概念的朋友可以去看 【資料結構 10】Trie｜字首樹｜字典樹 這個視訊，建立直覺的了解。

實際設計的時候，用字典樹去存儲，如果某個字元是一個單詞的結尾，那麼它的 isEnd 屬性設定為 true。

// javascript
var Trie = function() {
    this.children = {};
};

Trie.prototype.insert = function(word) {
    let node = this.children;
    for (const ch of word) {
        if (!node[ch]) {
            node[ch] = {};
        }
        node = node[ch];
    }
    node.isEnd = true;
};

Trie.prototype.searchPrefix = function(prefix) {
    let node = this.children;
    for (const ch of prefix) {
        if (!node[ch]) {
            return false;
        }
        node = node[ch];
    }
    return node;
}

Trie.prototype.search = function(word) {
    const node = this.searchPrefix(word);
    return node !== undefined && node.isEnd !== undefined;
};

Trie.prototype.startsWith = function(prefix) {
    return this.searchPrefix(prefix);
};