Lt211. 添加与搜索单词 - 数据结构设计

211. 添加与搜索单词 - 数据结构设计

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：

• WordDictionary() 初始化词典对象
• void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
• bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 ‘.’ ，每个 . 都可以表示任何一个字母。

​

示例：
输入： [“WordDictionary”,”addWord”,”addWord”,”addWord”,”search”,”search”,”search”,”search”] [[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[“.ad”],[“b..”]] 输出： [null,null,null,null,false,true,true,true] 解释： WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord(“bad”); wordDictionary.addWord(“dad”); wordDictionary.addWord(“mad”); wordDictionary.search(“pad”); // return False wordDictionary.search(“bad”); // return True wordDictionary.search(“.ad”); // return True wordDictionary.search(“b..”); // return True
​

提示：

• 1 <= word.length <= 500
• addWord 中的 word 由小写英文字母组成
• search 中的 word 由 ‘.’ 或小写英文字母组成
• 最多调用 50000 次 addWord 和 search

思路

哈希表存储对应字符长度的 set，search 时，先判断长度是否存在，不是的话返回 false，再判断对应的 set 中是否存在完全相同的单词，是的话返回 true。再在 set 中逐个匹配和 word 是不是完全相同，word 对应的每个 char 如果是.就跳过，如果不同就 break，最后判断匹配上的长度和 set 是否完全一致，是的话返回 true，没找到返回 false。

解答

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

/**
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function (word) {
  if (this.map.has(word.length)) {
    this.map.get(word.length).add(word);
  } else {
    this.map.set(word.length, new Set([word]));
  }
};

/**
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function (word) {
  if (!this.map.has(word.length)) return false;
  if (this.map.get(word.length).has(word)) return true;
  for (const set of this.map.get(word.length)) {
    let i;
    for (i = 0; i < set.length; i++) {
      if (word[i] === ".") {
        continue;
      }
      if (word[i] != set[i]) {
        break;
      }
    }
    if (i === set.length) {
      return true;
    }
  }
  return false;
};