难度: Medium
有个内含单词的超大文本文件，给定任意两个不同的单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?
示例：
输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student" 输出：1
提示：
words.length <= 100000
Submission
运行时间: 54 ms
内存: 32.6 MB
class Solution:
def findClosest(self, words: List[str], word1: str, word2: str) -> int:
# # 最小堆
# import heapq
# heap1 = []
# heap2 = []
# for i in range(len(words)):
# if words[i] == word1:
# heapq.heappush(heap1, i)
# if words[i] == word2:
# heapq.heappush(heap2, i)
# min_dis = 100000
# while heap1 and heap2:
# min_dis = min(min_dis, abs(heap1[0] - heap2[0]))
# if heap1[0] < heap2[0]:
# heapq.heappop(heap1)
# else:
# heapq.heappop(heap2)
# return min_dis
# 双指针
pre1 , pre2 = 100000, 100000
lw = len(words)
min_dis = 100000
for i in range(lw):
if words[i] == word1:
pre1 = i
min_dis = min(min_dis, abs(pre1 - pre2))
if words[i] == word2:
pre2 = i
min_dis = min(min_dis, abs(pre2 - pre1))
return min_dis
Explain
题解使用了双指针技术来找出两个指定单词的最短距离。首先，初始化两个指针 pre1 和 pre2 为一个非常大的数（题中使用了100000），这两个指针将分别记录最近一次遇到 word1 和 word2 的索引位置。然后遍历整个单词列表，每当找到一个 word1 或 word2，就更新相应的指针，并计算与另一个单词上次出现位置的距离，取所有这些距离的最小值作为结果。
时间复杂度: O(n)
空间复杂度: O(1)
# Find the closest distance between two words using two pointers
class Solution:
def findClosest(self, words: List[str], word1: str, word2: str) -> int:
# Initialize two pointers for the last seen positions of word1 and word2
pre1, pre2 = 100000, 100000
lw = len(words)
min_dis = 100000
for i in range(lw):
if words[i] == word1:
pre1 = i # Update last seen index for word1
min_dis = min(min_dis, abs(pre1 - pre2)) # Update min distance
if words[i] == word2:
pre2 = i # Update last seen index for word2
min_dis = min(min_dis, abs(pre2 - pre1)) # Update min distance
return min_dis
Explore
在初始化 pre1 和 pre2 为 100000 是为了设置一个足够大的初始值，这样即使第一次遇到 word1 或 word2，计算与另一个单词的距离时不会得到一个不合理的小值。一般情况下，这个值应该大于或等于 words 数组的最大可能长度，以确保它在任何合理的输入长度上都不会被误用为一个有效的索引。此选择不一定严格与 words 数组的实际长度相关，但应大于任何预期的数组长度，以避免任何潜在的计算错误。
在这种情况下，计算的距离依然是准确的。因为无论是 word1 还是 word2 作为遇到的第一个单词，只要更新了对应的 pre1 或 pre2 指针，距离的计算始终是基于最后一次遇到这两个单词的索引进行的。尽管初始化的 pre1 和 pre2 都非常大，但在任何一个单词被找到后，相应的索引就会被更新，因此计算出的距离将反映真实情况。
实际的题解代码中并没有直接提到关于多次查询优化的具体细节。然而，如果需要优化多次查询的情况，可以预处理 words 数组，创建两个字典或列表来存储每个单词出现的所有索引。这样，每次查询时，而不是重新遍历整个数组，我们可以直接访问这些预存的索引，使用更高效的方法（如双指针在两个排序列表上操作）来找到最小距离。这种预处理可以显著减少每次查询的时间复杂度，特别是在 words 数组很大或查询次数很多的场景下。