208. 实现 Trie (前缀树)

题目

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

题解

/**
 * Initialize your data structure here.
 */
var Trie = function() {
  this.isEnd = false;
  this.next = new Array(26);
};

/**
 * Inserts a word into the trie.
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
  let node = this;
  for (let w of word) {
    let index = w.charCodeAt() - "a".charCodeAt();
    if (!node.next[index]) {
      node.next[index] = new Trie();
    }
    node = node.next[index];
  }
  node.isEnd = true;
};

/**
 * Returns if the word is in the trie.
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
  let node = this;
  for (let w of word) {
    let index = w.charCodeAt() - "a".charCodeAt();
    node = node.next[index];
    if (!node) return false;
  }
  return node.isEnd;
};

/**
 * 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) {
  let node = this;
  for (let w of prefix) {
    let index = w.charCodeAt() - "a".charCodeAt();
    node = node.next[index];
    if (!node) return false;
  }
  return true;
};

/**
 * 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)
 */