难度: Easy
Submission
运行时间: 23 ms
内存: 18.4 MB
class Solution:
def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
index1 = []
index2 = []
for i in range(len(wordsDict)):
if wordsDict[i] == word1:
index1.append(i)
if wordsDict[i] == word2:
index2.append(i)
ans = []
for i in range(len(index1)):
for j in range(len(index2)):
ans.append(abs(index1[i]-index2[j]))
return min(ans)
Explain
该题解的思路是先遍历一遍单词列表，将字符串 word1 和 word2 出现的位置分别记录在 index1 和 index2 两个列表中。然后使用两个嵌套循环，计算 index1 中每个位置与 index2 中每个位置的绝对差值，并存入 ans 列表。最后返回 ans 列表中的最小值，即为最短单词距离。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
# 记录 word1 出现的位置
index1 = []
# 记录 word2 出现的位置
index2 = []
# 遍历单词列表
for i in range(len(wordsDict)):
if wordsDict[i] == word1:
index1.append(i)
if wordsDict[i] == word2:
index2.append(i)
# 存储所有可能的距离
ans = []
# 双重循环计算距离
for i in range(len(index1)):
for j in range(len(index2)):
ans.append(abs(index1[i]-index2[j]))
# 返回最短距离
return min(ans)
Explore
是的，有更高效的方法可以避免嵌套循环中的冗余计算。一种方法是使用双指针技术。首先，保持两个指针分别指向两个列表（index1 和 index2）。然后，比较两个指针指向的元素来确定哪个较小，并只移动较小元素的指针。每次移动指针时，计算两个指针指向的元素之间的距离，并更新最短距离。这种方法只需要线性时间复杂度，即 O(m + n)，其中 m 和 n 分别为两个列表的长度。
实际上可以在遍历过程中即时更新最短距离。通过使用一个变量来存储当前的最短距离，每次计算两个位置的距离时，立即比较并更新这个最短距离变量，这样就无需存储所有距离。这种即时更新策略显著降低了空间复杂度，从 O(m * n) 减少到 O(1)。
使用两个独立的 if 语句确实可能导致在某些情况下性能稍微下降，尤其是当 word1 和 word2 频繁交替出现时，因为每次遍历都需要分别检查两次。然而，这种性能下降通常是微小的，因为检查字符串相等性通常很快。如果对性能有极端要求，可以考虑使用一种更复杂的数据结构，例如字典，来一次遍历中处理所有单词的位置记录。
是的，这种做法确实会导致不必要的内存使用，尤其是当 index1 和 index2 的长度很大时。存储所有可能的位置差值可能导致内存消耗大量增加。更有效的做法是使用上述提到的即时更新策略，即在计算距离时直接更新最短距离，而不是存储所有距离。这样可以显著减少内存使用，只需维持几个变量即可。