题目

题目来源：力扣（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 。

示例：

输入
[“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树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。

Trie树的3个基本性质：

  1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
  2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符互不相同。
  1. var Trie = function () {
  2.   // 初始化根节点
  3.   // 根节点不保存任何信息
  4.   this.children = {};
  5. };
  7. /** 
  8.  * @param {string} word
  9.  * @return {void}
  10.  */
  11. Trie.prototype.insert = function (word) {
  12.   // 从字典树的根开始，插入字符串
  13.   let node = this.children;
  14.   for (const ch of word) {
  15.     // 子节点不存在，创建一个新的子节点
  16.     if (!node[ch]) {
  17.       node[ch] = {};
  18.     }
  19.     // 子节点存在,沿着指针移动到子节点，继续处理下一个字符
  20.     node = node[ch];
  21.   }
  22.   // 布尔字段 isEnd，表示该节点是否为字符串的结尾
  23.   node.isEnd = true;
  24. };
  26. /** 
  27.  * @param {string} prefix
  28.  * @return {void}
  29.  */
  30. Trie.prototype.searchPrefix = function (prefix) {
  31.   // 从字典树的根开始，查找前缀
  32.   let node = this.children;
  33.   for (const ch of prefix) {
  34.     // 子节点不存在，说明字典树中不包含该前缀，返回空指针
  35.     if (!node[ch]) {
  36.       return false;
  37.     }
  38.     // 子节点存在，沿着指针移动到子节点，继续搜索下一个字符
  39.     node = node[ch];
  40.   }
  41.   return node;
  42. }
  45. /** 
  46.  * @param {string} word
  47.  * @return {boolean}
  48.  */
  49. Trie.prototype.search = function (word) {
  50.   const node = this.searchPrefix(word);
  51.   // 若搜索到了前缀的末尾，就说明字典树中存在该前缀。
  52.   // 此外，若前缀末尾对应节点的 isEnd 为真，则说明字典树中存在该字符串
  53.   return node !== undefined && node.isEnd !== undefined;
  54. };
  56. /** 
  57.  * @param {string} prefix
  58.  * @return {boolean}
  59.  */
  60. Trie.prototype.startsWith = function (prefix) {
  61.   return this.searchPrefix(prefix);
  62. };
  64. /**
  65.  * Your Trie object will be instantiated and called as such:
  66.  * var obj = new Trie()
  67.  * obj.insert(word)
  68.  * var param_2 = obj.search(word)
  69.  * var param_3 = obj.startsWith(prefix)
  70.  */

参考资料：
https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode-ti500/
https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/fu-xue-ming-zhu-cong-er-cha-shu-shuo-qi-628gs/
https://blog.csdn.net/weixin_39778570/article/details/81990417