前缀树(Trie)-完整代码

• 结构
  • Node 定义
  • WordDictionary 定义
    • add <-- addNode调用
    • search <-- searchNode递归

class Node {
    constructor() {
        this.children = {};
        this.isEnd = false;
    }
}

class WordDictionary {
    constructor() {
        this.root = new Node();
    }

    addNode(currentNode, word) {
        for (const ch of word) {
            currentNode.children[ch] = currentNode.children[ch] || new Node();
            currentNode = currentNode.children[ch];
        }
        currentNode.isEnd = true;
    };

    add(word) {
        this.addNode(this.root, word);
    };

    searchNode(currentNode, word, i) {
        if (i === word.length) return currentNode.isEnd;
        const ch = word[i];
        if (ch in currentNode.children) {
            return this.searchNode(currentNode.children[ch], word, i + 1);
        } else {
            return false;
        }
    }

    search(word) {
        return this.searchNode(this.root, word, 0);
    }
}

(() => {
    let dictionary = new WordDictionary();
    dictionary.add("bin");
    dictionary.add("binary");
    dictionary.add("brother");
    console.log(dictionary.search("bin"));
    console.log(dictionary.search("binar"));
    console.log(dictionary.search("binary"));
    console.log(dictionary.search("bro"));
})()