211. Design Add and Search Words

添加与搜索单词，数据结构设计。

Trie 称为数字树或前缀树，是一种搜索有序树数据结构，主要用于对字符串进行高效的动态添加/搜索操作。

应用：自动完成搜索、拼写检查、T9预测文本，IP路由(最长前缀匹配)等。

如果用hash实现的情况下，时间复杂度O(m * n)。大型数据集的缩放，一旦哈希表的增加，会有很多哈希冲突，搜索时间复杂度可以增加到 O(n ^ 2 * m)，当存储具有许多相同前缀的键时，与hashmap相比，Trie可以使用更少的空间。

参考208，递归实现

• 时间复杂度O(n)，空间复杂度O(1)
• Runtime: 204 ms, faster than 94.91%
• Memory Usage: 60.1 MB, less than 53.40%

var WordDictionary = function() {
  this.map = {};
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
  let node = this.map;
  for (const ch of word) {
    if (!node[ch]) {
      node[ch] = {};
    }
    node = node[ch];
  }
  node.isEnd = true;
  // console.log(this.map)
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
  return this.searchInNode(word, this.map);
};


WordDictionary.prototype.searchInNode = function(word, node) {
  for (let i = 0; i < word.length; i++) {
    const ch = word[i];
    if (!node[ch]) {
      if (ch === '.') {
        for (let j in node) {
          if (this.searchInNode(word.substring(i + 1), node[j])) {
            return true;
          }
        }
      }
      return false;
    } else {
      node = node[ch];
    }
  }
  return node !== undefined && node.isEnd !== undefined;
};

/** 
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */