原文：208. 实现 Trie (前缀树)(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-0208/

题目：

难度：Middle

相关话题：设计、字典树

实现一个 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 构成的。

  • 保证所有输入均为非空字符串。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * Initialize your data structure here.
 */
var Trie = function() {
  this.tire={}
};

/**
 * Inserts a word into the trie.
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
  _insert(0,this.tire)
  function _insert(id,t){
    if(id===word.length)return
    if(t[word[id]]==null){
      t[word[id]]={}
    }
    if(id===word.length-1){
      t[word[id]].exact=true
    }
    _insert(id+1,t[word[id]])
  }
};

/**
 * Returns if the word is in the trie.
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
  return _search(0,this.tire)
  function _search(id,t){
    if(id===word.length)return !!t.exact
    if(t[word[id]]==null)return false
    return _search(id+1,t[word[id]])
  }
};

/**
 * 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) {
  return _startsWith(0,this.tire)
  function _startsWith(id,t){
    if(id===prefix.length)return true
    if(t[prefix[id]]==null)return false
    return _startsWith(id+1,t[prefix[id]])
  }
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = Object.create(Trie).createNew()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */