程序员面试金典 - 面试题 17.11. 单词距离

科技 06-18 来源：每日精选算法题

题目难度: 中等

原题链接[1]

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

示例：

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

提示：

words.length <= 100000

题目思考

重复多次查找时如何优化?

解决方案

方案 1

思路

我们可以维护两个单词的最后出现下标, 都初始化为-1, 代表尚未出现的情况
然后从头开始遍历, 遇到其中一个单词时, 就更新其最后出现下标
接下来检查另一个单词的最后出现下标, 如果它不是-1, 就说明得到了一个有效距离, 用它来更新最终结果即可
即使另一个单词在更早之前还出现过, 它和当前单词的距离一定大于最后出现下标和当前单词的距离
这就是为什么只需要维护两个单词的最后出现下标
下面的代码中对每个步骤都有注释, 方便大家理解
但这种方案存在一个问题: 如果需要重复多次查找, 则每次都要遍历整个文本文件, 效率较低, 这就引出了下面的方案 2

复杂度

时间复杂度 O(N): 只需要遍历数组一遍
空间复杂度 O(1): 只使用了几个常数空间的变量

代码

class Solution:
    def findClosest(self, words: List[str], word1: str, word2: str) -> int:
        # 单次遍历+维护两最后下标
        i1, i2 = -1, -1
        res = float("inf")
        for i, w in enumerate(words):
            if w == word1:
                # 更新单词1最后出现下标
                i1 = i
                if i2 != -1:
                    # 单词2前面出现过, 得到一个有效距离, 用它更新最终结果
                    res = min(res, i1 - i2)
            elif w == word2:
                # 更新单词2最后出现下标
                i2 = i
                if i1 != -1:
                    # 单词1前面出现过, 得到一个有效距离, 用它更新最终结果
                    res = min(res, i2 - i1)
        return res

方案 2

思路

方案 1 对于重复多次查找的表现不佳, 那如何优化呢?
我们可以使用预处理的思路, 预先建立一个单词到其所有下标的映射字典
这样查找时只需要遍历待查找的两个单词的所有下标即可
接下来利用双指针, 维护两单词当前下标, 对应的距离就是较大-较小下标
然后每次都移动较小的那个下标, 这样保证一定能遍历到最短的距离
下面的代码中对每个步骤都有注释, 方便大家理解

复杂度

时间复杂度 O(N+M): 预处理需要 O(N) (只需要一次), 每次查找需要 O(M) (M 是两个单词的下标个数之和)
空间复杂度 O(N): 额外下标字典

代码

class Solution:
    def findClosest(self, words: List[str], word1: str, word2: str) -> int:
        # 下标字典+双指针
        # 这里前提是words保持不变, 每次只变化word1和word2参数
        # 所以理论上下面的预处理部分应该放在单独的init函数
        # 预处理部分, 得到单词到其所有下标的映射字典
        d = collections.defaultdict(list)
        for i, w in enumerate(words):
            d[w].append(i)
        # 查找部分
        arr1, arr2 = d[word1], d[word2]
        i, j = 0, 0
        res = float("inf")
        while i < len(arr1) and j < len(arr2):
            # 更新最短距离
            res = min(res, abs(arr1[i] - arr2[j]))
            if arr1[i] < arr2[j]:
                # 单词1下标更小, 移动它
                i += 1
            else:
                # 单词2下标更小, 移动它
                j += 1
        return res