题目

题目来源：力扣（LeetCode）

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

实现 MagicDictionary 类：

MagicDictionary() 初始化对象
void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

示例：

输入
[“MagicDictionary”, “buildDict”, “search”, “search”, “search”, “search”]
[[], [[“hello”, “leetcode”]], [“hello”], [“hhllo”], [“hell”], [“leetcoded”]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict([“hello”, “leetcode”]);
magicDictionary.search(“hello”); // 返回 False
magicDictionary.search(“hhllo”); // 将第二个 ‘h’ 替换为 ‘e’ 可以匹配 “hello” ，所以返回 True
magicDictionary.search(“hell”); // 返回 False
magicDictionary.search(“leetcoded”); // 返回 False

  1. function Trie() {
  2.   this.map = {};
  3.   this.isEnd = false;
  4. }
  5. /**
  6.  * Initialize your data structure here.
  7.  */
  8. var MagicDictionary = function () {
  9.   this.root = [];
  10. };
  11. /**
  12.  * @param {string[]} dictionary
  13.  * @return {void}
  14.  */
  15. MagicDictionary.prototype.buildDict = function (dictionary) {
  16.   dictionary.forEach((item) => {
  17.     let tmp = new Trie();
  18.     this.insert(tmp, item);
  19.     this.root.push(tmp);
  20.   });
  21. };
  22. MagicDictionary.prototype.insert = function (node, word) {
  23.   for (let i = 0; i < word.length; i++) {
  24.     node.map[word[i]] = node.map[word[i]] || new Trie();
  25.     node = node.map[word[i]];
  26.   }
  28.   node.isEnd = true;
  29. };
  30. /**
  31.  * @param {string} searchWord
  32.  * @return {boolean}
  33.  */
  34. MagicDictionary.prototype.search = function (searchWord) {
  35.   return this.root.reduce((total, item) => {
  36.     return total || this.searchDfs(item, searchWord);
  37.   }, false);
  38. };
  39. MagicDictionary.prototype.searchDfs = function (node, searchWord) {
  40.   let flag = false;
  41.   for (let i = 0; i < searchWord.length; i++) {
  42.     if (node.map[searchWord[i]]) {
  43.       node = node.map[searchWord[i]];
  44.     } else if (!flag) {
  45.       flag = true;
  46.       let keys = Object.keys(node.map);
  47.       return keys.reduce((total, item) => {
  48.         return total || this.dfs(node.map[item], searchWord.slice(i + 1));
  49.       }, false);
  50.     } else {
  51.       return false;
  52.     }
  53.   }
  54.   return false;
  55. };
  56. MagicDictionary.prototype.dfs = function (node, word) {
  57.   for (let i = 0; i < word.length; i++) {
  58.     if (node.map[word[i]]) {
  59.       node = node.map[word[i]];
  60.     } else {
  61.       return false;
  62.     }
  63.   }
  64.   return node.isEnd;
  65. };
  67. /**
  68.  * Your MagicDictionary object will be instantiated and called as such:
  69.  * var obj = new MagicDictionary()
  70.  * obj.buildDict(dictionary)
  71.  * var param_2 = obj.search(searchWord)
  72.  */