208. Implement Trie (Prefix Tree)

Leetcode link

题目简介

var Trie = function() {};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {};

这题要求我们自己构造一个 字典树 并完成 insert，search，startsWith 三个方法的设计

解题思路

字典树的根节点一般是空节点，而且每一个节点只会存储字符串的其中一个字符

每个节点中会包含两种信息：

1. 下一个字符的信息，有两种存储方式：一个长度为 26 的数组、Map
2. 当前节点是否为某个字符串的最后一个字符节点

因为题目测试量小，用数组容易造成空间浪费，所以我们选择 Map，最后一个节点的标识符我们用布尔值 isEnd 来表示

Javascript

class TrieNode {
    constructor() {
        this.children = new Map()
        this.isEnd = false
    }
}


var Trie = function () {
    this.root = new TrieNode()
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
    let cur = this.root
    for (const char of word) {
        if (!cur.children.has(char)) {
            cur.children.set(char, new TrieNode())
        }
        cur = cur.children.get(char)
    }
    cur.isEnd = true
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
    let cur = this.root
    for (const char of word) {
        if (cur.children.has(char)) {
            cur = cur.children.get(char)
        } else {
            return false
        }
    }
    return cur.isEnd
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
    let cur = this.root
    for (const char of prefix) {
        if (cur.children.has(char)) {
            cur = cur.children.get(char)
        } else {
            return false
        }
    }
    return true
};