Day272:设计一个支持两种操作的数据结构

[Genzhen]

addWord(word) // 添加字符串
search(word)   // 返回布尔值，是否存在
//search可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。
// . 可以表示任何一个字母。

// 示例
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
// 可以假设所有单词都是由小写字母 a-z 组成的。

---

每日一题会在下午四点在交流群集中讨论，五点小程序中更新答案 欢迎大家在下方发表自己的优质见解

二维码加载失败可点击 小程序二维码

扫描下方二维码，收藏关注，及时获取答案以及详细解析，同时可解锁800+道前端面试题。

---

思路分析

这道题要求字符串既可以被添加、又可以被搜索，这就意味着字符串在添加时一定要被存在某处。键值对存储，可以用 Map(或对象字面量来模拟 Map)。

注意：为了降低查找时的复杂度，我们可以考虑以字符串的长度为 key，相同长度的字符串存在一个数组中，这样可以提高后续定位的效率

难点在于 search 这个 API，它既可以搜索文字，又可以搜索正则表达式。所以在搜索前需要额外判断一下，传入的到底是普通字符串，还是正则表达式。如果是普通字符串，则直接去 Map 中查找是否有这个 key;如果是正则表达式，则创建一个正则表达式对象，判断 Map 中相同长度的字符串里，是否存在一个能够与这个正则相匹配。

参考实现

/**
 * 构造函数
 */
const WordDictionary = function () {
  // 初始化一个对象字面量
  this.words = {};
};
/**
 * 添加字符串方法
 */
WordDictionary.prototype.addWord = function (word) {
  // 若该字符串对应的长度的数组已经存在，则只添加
  const len = word.length;
  if (this.words[len]) {
    this.words[len].push(word);
  } else {
    // 不存在，先创建
    this.words[len] = [word];
  }
};
/**
 * 搜索方法
 */
WordDictionary.prototype.search = function (word) {
  const len = word.length;
  // 若该字符串长度在Map中对应的数组长度不存在，则该字符串不存在
  if (!this.words[len]) {
    return false;
  }
  // 判断是否存在.,不包含一定是普通字符串
  if (!word.includes(".")) {
    // 定位到和目标字符穿长度一致的字符串数组，查找是否存在
    return this.words[len].includes(word);
  }
  // 否则是正则表达式
  const reg = new RegExp(word);
  return this.words[len].some((item) => {
    return reg.test(item);
  });
};

[savoygu]

搜索单词时间复杂度： O(N^2)

class Word {
  constructor() {
    this.words = new Set()
  }

  addWord(word) {
    this.words.add(word)
  }

  search(word1) {

    function compareWord(word1, word2) {
      const wLen1 = word1.length, wLen2 = word2.length
      if (wLen1 !== wLen2) return false

      let i = 0
      while(i < wLen1) {
        if (word1[i] === '.') {
          i++
          continue
        }

        if (word1[i] !== word2[i]) {
          return false
        }

        i++
      }

      return true
    }

    for (const word2 of this.words) {
      if (compareWord(word1, word2)) {
        return
      }
    }
    return false
  }
}

[doudou673]

function Word() {
  this.word = new Set()
}

Word.prototype.addWord = function (string) {
  this.word.add(string)
}

Word.prototype.search = function (string) {
  if (this.word.has(string)) return true
  let reg = new RegExp(string)
  let words = [...this.word].join()
  return reg.test(words)
}

[savoygu]

搜索单词时间复杂度： O(N^2)

class Word {
  constructor() {
    this.words = new Set()
  }

  addWord(word) {
    this.words.add(word)
  }

  search(word1) {

    function compareWord(word1, word2) {
      const wLen1 = word1.length, wLen2 = word2.length
      if (wLen1 !== wLen2) return false

      let i = 0
      while(i < wLen1) {
        if (word1[i] === '.') {
          i++
          continue
        }

        if (word1[i] !== word2[i]) {
          return false
        }

        i++
      }

      return true
    }

    for (const word2 of this.words) {
      if (compareWord(word1, word2)) {
        return
      }
    }
    return false
  }
}

思路借鉴：对单词按单词长度分组

class Word {
  constructor() {
    this.words = new Map()
  }

  addWord(word) {
    const wLen = word.length
    const words = this.words.get(wLen)
    const added = words && words.add(word)
    if (!added) {
      this.words.set(wLen, new Set([word]))
    }
  }

  search(word) {
    const wLen = word.length
    const words = this.words
    if (!words.has(wLen)) return false

    if (!word.includes('.')) {
      return words.get(wLen).has(word)
    }

    const reg = new RegExp(word)
    return [...words.get(wLen)].some(word => reg.test(word))
  }
}