LeetCode题解：208. 实现 Trie (前缀树)，对象，JavaScript，详细注释

[chencl1986]

原题链接：208. 实现 Trie (前缀树)

解题思路：

1. 前缀树的每一个节点都用给一个对象表示。
2. 单词的每个字母都作为一个节点的key，其value为一个对象。
3. 在单词结束的节点，插入key和value都为EOF表示单词在此结束。
4. 进行插入操作时，将每个字母作为一个节点，按顺序插入到前缀树中。
5. 进行搜索时，按字母顺序在前缀树中查询，遇到EOF表示单词在前缀树中。

/**
 * Initialize your data structure here.
 */
var Trie = function () {
  // 根节点使用一个空对象，单词的每个字母作为对象的一个key
  this.root = {};
  // 使用一个固定的标记，标记一个节点为前缀树的根节点
  // 此处使用Symbol标记，避免重复
  this.endOfWord = Symbol('EOF');
};

/**
 * Inserts a word into the trie.
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
  // 当一个单词插入前缀树时，都从根节点开始插入
  let node = this.root;

  // 逐个字母遍历单词
  for (const char of word) {
    // 如果字母未在前缀树中川建国节点，则创建一个新节点
    node[char] = node[char] || {};
    // 移动节点，向下遍历
    node = node[char];
  }

  // 标记当前节点是一个单词的结束位置
  node[this.endOfWord] = this.endOfWord;
};

/**
 * Returns if the word is in the trie.
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  // 单词的搜索从根节点开始
  let node = this.root;

  // 在前缀树中查找单词的每个字母
  for (const char of word) {
    // 如果当前字母不存在于前缀树，该单词也一定不存在
    if (!node[char]) {
      return false;
    }

    // 移动节点，向下查找
    node = node[char];
  }

  // 如果该单词的最后一个字母对应的节点，在前缀树中被标记为单词结尾，才表示这个单词在前缀树中存在
  return node[this.endOfWord] === this.endOfWord;
};

/**
 * 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.root;

  // 在前缀树中查找单词的每个字母
  for (const char of prefix) {
    // 如果当前字母不存在于前缀树，该单词也一定不存在
    if (!node[char]) {
      return false;
    }

    // 移动节点，向下查找
    node = node[char];
  }

  // 此处无需判断单词是否完整的在前缀树中存在，只要前缀树中存在单词所有字母即可
  return true;
};