208. 实现 Trie (前缀树)（JS实现）

小灰灰 2022-11-25 13:06 124阅读 0赞

## 1 题目 ##

> 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。  
> 示例:  
> Trie trie = new Trie();  
> trie.insert(“apple”);  
> trie.search(“apple”); // 返回 true  
> trie.search(“app”); // 返回 false  
> trie.startsWith(“app”); // 返回 true  
> trie.insert(“app”);  
> trie.search(“app”); // 返回 true  
> 说明:  
> 你可以假设所有的输入都是由小写字母 a-z 构成的。  
> 保证所有输入均为非空字符串。

链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree

## 2 思路 ##

**这道题就是实现前缀树这种数据结构，这种数据结构有个特点，就是每个节点存储一个元素为指针的数组，数组的索引就指明当前的字母，而数组值就指向下一个指针数组。**

## 3代码 ##

/** * Initialize your data structure here. */
    var Trie = function() { 
        this.startIndex = 'a'.charCodeAt();
        this.root = new TreeNode();
    };
    
    /** * Inserts a word into the trie. * @param {string} word * @return {void} */
    Trie.prototype.insert = function(word) { 
        let p = this.root;
        for (let i=0; i<word.length; i++) { 
            let index = word[i].charCodeAt() - this.startIndex;
            if (!p.list[index]) { 
                let newNode = new TreeNode();
                p.list[index] = newNode;
            }
            p = p.list[index];
        }
        p.type = 'leaf';
        p.word = word;
    };
    
    /** * Returns if the word is in the trie. * @param {string} word * @return {boolean} */
    Trie.prototype.search = function(word) { 
        let p = this.root;
        for (let i=0; i<word.length; i++) { 
            p = p.list[word[i].charCodeAt() - this.startIndex];
            if (!p && i<word.length-1) return false;
        }
    
        if (p && p.type === 'leaf' && p.word === word) return true;
        return false;
    };
    
    /** * 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 p = this.root;
        for (let i=0; i<prefix.length; i++) { 
            p = p.list[prefix[i].charCodeAt() - this.startIndex];
            if (!p) return false;
        }
        return true;
    };
    
    function TreeNode() { 
        this.type = 'branch';
        this.list = [];
        this.word = '';
    }
    
    /** * 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) */