困难

问题描述

设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

实现 WordFilter 类：

• WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
• f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。

示例：

输入
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
输出
[null, 0]
解释
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suff = "e" 。

提示：

• 1 <= words.length <= 104
• 1 <= words[i].length <= 7
• 1 <= pref.length, suff.length <= 7
• words[i]、pref 和 suff 仅由小写英文字母组成
• 最多对函数 f 执行 104 次调用

暴力

根据题目给出的数据范围，单个单词长度只有 $7$，单词数量为 $10^4$，单次最坏情况是的计算量是 $2 \times 7 \times 10^4 = 1.4 \times 10^5$，但是调用此时最多是 $10^4$ 次，暴力对每个单词的前后缀进行匹配，能不能过就要看脸了。

/**
 * @param {string[]} words
 */
var WordFilter = function (words) {
  this.words = words
}

/**
 * @param {string} pref
 * @param {string} suff
 * @return {number}
 */
WordFilter.prototype.f = function (pref, suff) {
  loop: for (let i = this.words.length - 1; i > -1; i--) {
    const word = this.words[i]
    for (let j = 0; j < pref.length; j++) {
      if (word[j] !== pref[j]) continue loop
    }
    for (let j = 1; j <= suff.length; j++) {
      if (word[word.length - j] !== suff[suff.length - j]) continue loop
    }
    return i
  }
  return -1
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * var obj = new WordFilter(words)
 * var param_1 = obj.f(pref,suff)
 */

• 时间复杂度：初始化操作复杂度为 $O(1)$，检索操作复杂度为 $O(\sum_{i = 0}^{n - 1} w_i)$，$w_i$ 为对应单词字符个数。
• 空间复杂度：$O(\sum_{i = 0}^{n - 1} w_i)$，$w_i$ 为对应单词字符个数。

前缀树 + 后缀树

分并构建前缀树和后缀树，记录每个前缀和后缀的单词下标，查找时分并对前缀树和后缀树进行搜索，搜索出对应的下标列表，再从搜索出来的下标列表的交集中找出最大值。

/**
 * @param {string[]} words
 */
var WordFilter = function (words) {
  const prefTree = {}
  const suffTree = {}
  for (let i = 0; i < words.length; i++) {
    const word = words[i]
    let tree
    tree = prefTree
    for (let j = 0; j < word.length; j++) {
      const char = word[j]
      if (!tree[char]) tree[char] = { idxs: [] }
      tree = tree[char]
      tree.idxs.push(i)
    }
    tree = suffTree
    for (let j = word.length - 1; j > -1; j--) {
      const char = word[j]
      if (!tree[char]) tree[char] = { idxs: [] }
      tree = tree[char]
      tree.idxs.push(i)
    }
  }
  this.prefTree = prefTree
  this.suffTree = suffTree
}

/**
 * @param {string} pref
 * @param {string} suff
 * @return {number}
 */
WordFilter.prototype.f = function (pref, suff) {
  let prefIdxs
  let suffIdxs
  let tree
  tree = this.prefTree
  for (let i = 0; i < pref.length; i++) {
    const char = pref[i]
    if (!tree[char]) return -1
    tree = tree[char]
  }
  prefIdxs = tree.idxs
  tree = this.suffTree
  for (let i = suff.length - 1; i > -1; i--) {
    const char = suff[i]
    if (!tree[char]) return -1
    tree = tree[char]
  }
  suffIdxs = tree.idxs
  const n = prefIdxs.length
  const m = suffIdxs.length
  for (let i = n - 1, j = m - 1; i >= 0 && j >= 0; ) {
    if (prefIdxs[i] < suffIdxs[j]) j--
    else if (prefIdxs[i] > suffIdxs[j]) i--
    else return prefIdxs[i]
  }
  return -1
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * var obj = new WordFilter(words)
 * var param_1 = obj.f(pref,suff)
 */

• 时间复杂度：初始化操作复杂度为 $O(\sum_{i = 0}^{n - 1} w_i)$，$w_i$ 为对应单词字符个数。检索操作复杂度为 $O(a + b + c)$，$a$ 和 $b$ 为前缀和后缀树的搜索次数，最大为 $7$，$n$ 为候选左边的个数。
• 空间复杂度：$O(\sum_{i = 0}^{n - 1} w_i)$，$w_i$ 为对应单词字符个数。

字典树

还可以通过枚举后缀拼接前缀的方式，将各种组合放入字典树中，然后查找时使用相同的方式对前后缀进行拼接后查找。

/**
 * @param {string[]} words
 */
var WordFilter = function (words) {
  const tree = {}
  for (let i = 0; i < words.length; i++) {
    const word = words[i]
    for (let j = 0; j < word.length; j++) {
      const target = word.slice(j) + '#' + word
      let node = tree
      for (let c of target) {
        if (!node[c]) node[c] = {}
        node = node[c]
        node.idx = i
      }
    }
  }
  this.tree = tree
}
/**
 * @param {string} pref
 * @param {string} suff
 * @return {number}
 */
WordFilter.prototype.f = function (pref, suff) {
  let tree = this.tree
  const target = `${suff}#${pref}`
  for (const char of target) {
    if (!tree[char]) return -1
    tree = tree[char]
  }
  return tree.idx
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * var obj = new WordFilter(words)
 * var param_1 = obj.f(pref,suff)
 */

• 时间复杂度：初始化操作复杂度为 $O(\sum_{i = 0}^{n - 1} w_i^2)$，$w_i$ 为对应单词字符个数。检索操作复杂度为 $O(a + b)$，$a$ 和 $b$ 为前缀和后缀树的长度。
• 空间复杂度：$O(\sum_{i = 0}^{n - 1} w_i)$，$w_i$ 为对应单词字符个数。