中等

问题描述

有个内含单词的超大文本文件，给定任意两个不同的单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?

示例：

输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"
输出：1

提示：

• words.length <= 100000

双指针

遍历单词数组，使用 $idx1$ 记录 $word1$ 的下标，$idx2$ 记录 $word2$ 的下标，若遇到相同字符串时，记录对应下标，当两个指针都已被移动时，计算两个指针的距离，并且更新最小距离。当最小距离为 $1$ 时，已经是最短距离了，可以直接返回。

/**
 * @param {string[]} words
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var findClosest = function (words, word1, word2) {
  let ans = Infinity
  let idx1 = -1
  let idx2 = -1
  const n = words.length
  for (let i = 0; i < n; i++) {
    if (words[i] === word1) idx1 = i
    if (words[i] === word2) idx2 = i
    if (idx1 >= 0 && idx2 >= 0) ans = Math.min(ans, Math.abs(idx1 - idx2))
    if (ans === 1) return 1
  }
  return ans
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

进阶：对于多次查询，我们可以使用哈希表缓存每个单词的所有下标，再从哈希表中取出两个单词的下标，计算最小距离。

/**
 * @param {string[]} words
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var findClosest = function (words, word1, word2) {
  const map = new Map()
  for (let i = 0; i < words.length; i++) {
    const arr = map.get(words[i]) || []
    arr.push(i)
    map.set(words[i], arr)
  }
  const idxs1 = map.get(word1)
  let n = idxs1.length
  const idxs2 = map.get(word2)
  let m = idxs2.length
  let min = Infinity
  while (n > 0 && m > 0) {
    const idx1 = idxs1[n - 1]
    const idx2 = idxs2[m - 1]
    min = Math.min(min, Math.abs(idx1 - idx2))
    if (min === 1) return 1
    if (idx1 > idx2) {
      n--
    } else {
      m--
    }
  }
  return min
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$