乐趣区

js实现Trie字典树

jiezi

前端实现字典树

本文演示前端实现字典树，同时这也是 LeetCode 第 208 题，medium 难度的题。

题目概述

实现一个 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 构成的。
保证所有输入均为非空字符串。

代码实现

树节点

首先声明树节点，每个节点有一个值、26 个孩子节点，用 {} 对象表示，其中每个对象存的是 TreeNode。
还有一个 isWord 属性用来存当前有没有以当前节点的 val 字符结尾的单词。

class TreeNode{constructor(val) {
        this.val = val
        this.isWord = false;
        this.chilrden = {}}

}

字典树构造函数

初始化字典树，只有根元素，根元素也是一个节点，所以用 TreeNode（）
同时根元素没有 val，故 TreeNode 不需要传参数。
暂时没有子元素，所以它的 children 属性暂时是：{} 空对象
也没有一个单词是不包含任何字母的，所以根的 isWord 属性也是走默认的 false

/**
 * Initialize your data structure here.
 */
var Trie = function() {this.root = new TreeNode();
};

实现 insert 方法

/**
 * Inserts a word into the trie.
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let curNode = this.root;
    let arr = word.split('')
    for(let i = 0; i < arr.length; i++){let isHasChildNode = curNode.chilrden[arr[i]]
        // 没有子节点的话，就要创建一个以当前字符为 val 的子节点
        if(!isHasChildNode){curNode.chilrden[arr[i]] = new TreeNode(arr[i])
        }
        curNode = curNode.chilrden[arr[i]]
        // 遍历到最后一个字符所对应的节点，将这个节点的 isWord 属性设为 true。if(i === arr.length - 1){curNode.isWord = true;}
    }
};

实现 search 方法

/**
 * Returns if the word is in the trie.
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let curNode = this.root;
    let arr = word.split('')
    for(let i = 0; i < arr.length; i++){if(!curNode.chilrden[arr[i]]){return false;}
        curNode = curNode.chilrden[arr[i]]
        // 搜素到最后一个字符，根据 isWord 属性判断是否曾经存过这个单词
        if(i === arr.length - 1){return curNode.isWord === true}
    }
};

实现 startswith 方法

/**
 * 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 curNode = this.root;
    let arr = prefix.split('')
    for(let i = 0; i < arr.length; i++){
        // 凡是查找的单词的中间某个字符，没有找到节点的，返回 false
        if(!curNode.chilrden[arr[i]]){return false;}
        curNode = curNode.chilrden[arr[i]]
    }
    // 每个字符都找到了节点，返回 true
    return true
};

测试代码

let trie = new Trie();
trie.insert(“apple”);
console.log(trie.search(“apple”)); // 返回 true
console.log(trie.search(“app”)); // 返回 false
console.log(trie.startsWith(“app”)); // 返回 true
trie.insert(“app”);
console.log(trie.search(“app”)); // 返回 true

我的前端算法库

地址：https://github.com/cunzaizhuy…
目前已经刷了 200 多道题，题解都在里面。

欢迎 star 和交流。

退出移动版