这是我参与更文挑战的第 30 天，活动详情查看更文挑战

这个系列没啥花头，就是纯 leetcode 题目拆解分析，不求用骚气的一行或者小众取巧解法，而是用清晰的代码和足够简单的思路帮你理清题意。让你在面试中再也不怕算法笔试。

141. 实现 Trie (前缀树/字典树) (implement-trie-prefix-tree)

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例 1

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
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
复制代码

基本思路

主要让我们认识了一个数据结构 Trie

Tire 树也叫字典树。它是一个树形结构，专门用来处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。例如搜索引擎的提示

蓝框就是提示，那么这种词条太多了海量，如何快速匹配输入内容，就用这种方式用空间换时间。这图是例子，不是说 google 就是这种结构。

下面举个例子来说明

用 how，hi，her，hello，so，see 作为数据集建立 trie 树

插入过程如下

由根到叶子的路径就是一个单词。红色的点就是叶子，一个字符串的终点。

最后变成这样

这样根据前缀来匹配字符串效率当然比遍历要高很多，核心是以空间换时间。

而存储方式就是通过一个下标与字符一一映射的数组来存储子节点的指针。

写法实现

实现其实不是很难，看代码和注释应该很清晰。

var Trie = function() {
  this.children = {}
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let node = this.children;
    for (const ch of word) {
        if (!node[ch]) {
            node[ch] = {};
        }
        node = node[ch];
    }
    node.isEnd = true;
};


Trie.prototype.searchPrefix = function(prefix) {
  let node = this.children
  for (ch of prefix) {
    if (!node[ch]) {
      return false
    }
    node = node[ch]
  }
  return node
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
  let node = this.searchPrefix(word)
  return node !== undefined && node.isEnd !== undefined
};

Trie.prototype.startsWith = function(prefix) {
  return Boolean(this.searchPrefix(prefix))
};

// 测试
let trie = new Trie();
trie.insert("apple");
// 我们此时打印的话, 看看insert 之后 trie 结构, 这样就很清晰了
// console.log(trie)
// {
//     "children":{
//         "a":{
//             "p":{
//                 "p":{
//                     "l":{
//                         "e":{
//                             "isEnd":true
//                         }
//                     }
//                 }
//             }
//         }
//     }
// }
console.log(trie.search("apple")) 
// 返回 true, 能查到，且isEnd 为 true 说明到末尾了
console.log(trie.search("app"))
// 返回 false，因为没到末尾，所以只能说匹配到前缀而不是单词
console.log(trie.startsWith("app"))
// 这次找到前缀就行

trie.insert("app");
// console.log(trie)
// {
//     "children":{
//         "a":{
//             "p":{
//                 "p":{
//                     "l":{
//                         "e":{
//                             "isEnd":true
//                         }
//                     },
//                     "isEnd":true  // 这里也有一个 app 的单词结尾了
//                 }
//             }
//         }
//     }
// }

console.log(trie.search("app"))
// true
复制代码

另外向大家着重推荐下这个系列的文章，非常深入浅出，对前端进阶的同学非常有作用，墙裂推荐！！！核心概念和算法拆解系列

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦点击此处交个朋友
Or 搜索我的微信号infinity_9368，可以聊天说地
加我暗号 “天王盖地虎” 下一句的英文，验证消息请发给我
presious tower shock the rever monster，我看到就通过，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧