题目描述

给定一个单词列表 words 和两个单词 word1 和 word2，返回这两个单词在列表中的最短距离。如果 word1 和 word2 是同一个单词，则返回它与自身的最近距离。

示例

示例 1:

输入: words = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
输出: 1

示例 2:

输入: words = ["practice", "makes", "perfect", "makes"], word1 = "makes", word2 = "makes"
输出: 2

题解

这个问题可以通过遍历数组并跟踪 word1 和 word2 的最近出现位置来解决。

1. 初始化：创建两个变量 index1 和 index2 来存储 word1 和 word2 的索引，并将它们初始化为 -1。同时，创建一个变量 minDistance 来存储最小距离，并将其初始化为 ∞。
2. 遍历数组：遍历单词列表 words。
   ○ 如果当前单词等于 word1，则更新 index1 为当前索引，并更新 minDistance 为 index1 和 index2 之间的距离。
   ○ 如果当前单词等于 word2，则更新 index2 为当前索引，并更新 minDistance 为 index1 和 index2 之间的距离。
   ○ 每次更新 minDistance 时，使用 min(minDistance, abs(index1 - index2)) 来确保它是最小的。
3. 返回结果：遍历结束后，返回 minDistance。

代码实现

int shortestDistance(vector<string>& words, string word1, string word2) {int index1 = -1, index2 = -1;int minDistance = INT_MAX;for (int i = 0; i < words.size(); i++) {if (words[i] == word1) {index1 = i;if (index2 != -1) {minDistance = min(minDistance, abs(index1 - index2));}}if (words[i] == word2) {index2 = i;if (index1 != -1) {minDistance = min(minDistance, abs(index1 - index2));}}}return minDistance;
}

复杂度分析

● 时间复杂度：O(n)，其中 n 是单词列表 words 的长度。我们需要遍历一次列表。
● 空间复杂度：O(1)，因为我们只使用了常数个额外变量。
这个算法的优势在于它只需要一次遍历即可找到最短单词距离，且不需要额外的存储空间。