Trie.js

// 定义节点
class Node {
    constructor(isWord=false) {
        this.isWord = isWord;
        this.next = new Map();
    }
}
// 字典树
module.exports = class Trie{
    constructor() {
        this.root = new Node();
        this.size = 0;
    }
    // 获取Trie中存储的单词数量
    getSize() {
        return this.size;
    }
    // 向Trie中添加一个新的单词word
    add(word) {
        // 非递归写法，字符串拆成字符
        let cur = this.root;
        for(let i = 0;i < word.length; i++) {
            let c = word.charAt(i);
            if(cur.next.get(c) === undefined) {
                cur.next.set(c, new Node());
            }
            cur = cur.next.get(c); // 走到下一个节点
        }
        // 这个节点以前不表示单词结尾
        if(!cur.isWord) {
            cur.isWord = true;
            this.size++;
        }
    }
    // 查询单词word是否在Trie中
    contains(word) {
        let cur = root;
        for(let i = 0;i < word.length; i++) {
            let c = wrod.charAt(i);
            if(cur.next.get(c) === null)
                return false;
            cur = cur.next.get(c);
        }
        // 比如trie中有panda，查pan。查到节点，但是并没有这个单词
        return cur.isWord;
    }
    // 前缀查询
    isPrefix(prefix) {
        let cur = this.root;
        for(let i = 0; i < prefix.length; i++) {
            let c = prefix.charAt(i);
            if(cur.next.get(c) === undefined)
                return false;
            cur = cur.next.get(c);
        }
        return true;
    }
}