Trie树

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

优点：利用公共前缀减少查询时间，最大限度减少无谓字符串比较，查询效率比哈希树高。

图片理解

var Trie = function () {
  this.root = {}
};
/** 
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function (word) {
  let cur = this.root
  for (let c of word) {
    if (!cur[c]) {
      cur[c] = {}
    }
    cur = cur[c]
  }
  cur.isEnd = true
};
/**
查找前缀的公共方法
*/
Trie.prototype.searchPrefix = function(prefix) {
  let cur = this.root
  for (let c of prefix) {
    if (!cur[c]) {
      return false
    }
    cur = cur[c]
  }
  return cur
}
/** 
* @param {string} word
* @return {boolean}
* return这句，如果不是End节点，不为false 而是 undefine 
*/
Trie.prototype.search = function (word) {
  const node = this.searchPrefix(word)
  return node != undefined && node.isEnd != undefined
};
/** 
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function (prefix) {
  return this.searchPrefix(prefix)
};
/**
* Your Trie object will be instantiated and called as such:
* var obj = new Trie()
* obj.insert(word)
* var param_2 = obj.search(word)
* var param_3 = obj.startsWith(prefix)
 */

参考文献：

1. CSDN