面试题 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}
 */
var findClosest = function (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}
 */
var findClosest = function (words, word1, word2) {
  let ans = words.length - 1;
  const cacheList1 = wordsMap.get(word1);
  const cacheList2 = wordsMap.get(word2);
  if (cacheList1 && cacheList2) {
    // 表中有值说明不是第一次，可以直接从表中的数据对比出结果
    for (let i of cacheList1) {
      for (let 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;
};