面试题 17.11. 单词距离

面试题 17.11. 单词距离

leetcode 链接

解法一：一次遍历

初始化三个变量 ans、index1、index2 分别用来保存最终结果、word1的最新下标 和 word2 的最新下标，遍历过程中不断更新。

如果 index1 和 index2 的差值为 1，则可以直接返回，因为最小值不可能比 1 更小。

/**
 * @param {string[]} words
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
function findClosest(words, word1, word2) {
  let ans = words.length - 1
  let index1, index2
  for (let i = 0; i < words.length; i++) {
    if (words[i] === word1) {
      if (index2) {
        const diff = i - index2
        if (diff === 1)
          return 1
        ans = Math.min(diff, ans)
      }
      index1 = i
    }
    else if (words[i] === word2) {
      if (index1) {
        const diff = i - index1
        if (diff === 1)
          return 1
        ans = Math.min(diff, ans)
      }
      index2 = i
    }
  }
  return ans
}

进阶

题目：如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?

维护一个 hash 表（这里用 Map 结构实现），存放每个单词下标组成的数组。

除了第一次查找时需要遍历一次文件，后面只需要从 hash 表中取出两个单词的下标列表，遍历对比取最小差值即可。

const wordsMap = new Map() // 用来存放单词下标的 hash 表

/**
 * @param {string[]} words
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
function findClosest(words, word1, word2) {
  let ans = words.length - 1
  const cacheList1 = wordsMap.get(word1)
  const cacheList2 = wordsMap.get(word2)
  if (cacheList1 && cacheList2) {
    // 表中有值说明不是第一次，可以直接从表中的数据对比出结果
    for (const i of cacheList1) {
      for (const j of cacheList2) {
        const diff = Math.abs(j - i)
        if (diff === 1)
          return 1
        ans = Math.min(diff, ans)
      }
    }
    return ans
  }
  // 表中无值则为第一次，需要遍历一次
  let index1, index2
  for (let i = 0; i < words.length; i++) {
    if (words[i] === word1) {
      if (index2) {
        const diff = i - index2
        if (diff === 1)
          return 1
        ans = Math.min(diff, ans)
      }
      index1 = i
    }
    else if (words[i] === word2) {
      if (index1) {
        const diff = i - index1
        if (diff === 1)
          return 1
        ans = Math.min(diff, ans)
      }
      index2 = i
    }
    const curList = wordsMap.get(words[i]) || []
    curList.push(i)
    wordsMap.set(words[i], curList)
  }
  return ans
}