题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
有个内含单词的超大文本文件，给定任意两个不同的单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?
示例：
- 输入：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
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号