题目

请你实现 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类的构造函数中，先声明了一个空对象作为根节点的children属性，然后我们在Trie类的原型上创建insert方法和searchPrefix方法以及search方法还有startsWith方法，这些方法中每一个都代表这一个功能，insert方法用于向Trie树中插入一个字符串，它首先获取根节点的children属性，然后遍历字符串中的每个字符，对于每个字符，如果在当前节点的children属性中不存在该字符，则在children中添加一个新的键值对，键为该字符，值为一个新的空对象，然后我们将节点指向该字符对应的对象，以便继续处理下一个字符，最后我们将该节点的isEnd属性设置为true，表示该节点是一个单词的结尾，searchPrefix方法用于查找以指定前缀开始的字符串，它首先获取根节点的children属性，然后遍历前缀字符串中的每个字符，对于每个字符如果在当前节点的children属性中不存在该字符，我们则返回false，否则将节点指向该字符对应的对象，以便继续处理下一个字符，最后返回最终节点对象，search方法用于查找指定字符串是否在Trie树中，它首先调用searchPrefix方法获取以该字符串为前缀的节点对象，然后判断该节点是否存在且isEnd属性是否为true，如果是则说明该字符串存在于Trie树中，startsWith方法用于判断Trie树中是否存在以指定前缀开始的字符串，它调用searchPrefix方法获取以该前缀为前缀的节点对象，如果节点对象存在则说明存在以该前缀开始的字符串，然后我们直接返回该节点对象即可

 var Trie = function () {
   this.children = {}
 }
 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 (const ch of prefix) {
     if (!node[ch]) {
       return false
     }
     node = node[ch]
   }
   return node
 }
 Trie.prototype.search = function (word) {
   const node = this.searchPrefix(word)
   return node !== undefined && node.isEnd !== undefined
 }
 Trie.prototype.startsWith = function (prefix) {
   return this.searchPrefix(prefix)
 }