LeetCode第245题_最短单词距离III
LeetCode第245题：最短单词距离III
问题描述
给定一个字符串数组 wordsDict 和两个字符串 word1 和 word2，返回列表中这两个单词之间的最短距离。
注意，word1 和 word2 可能是同一个单词，且它们在列表中可能会出现多次。word1 和 word2 是区分大小写的。
难度：中等
示例
示例 1:
输入: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
输出: 1
示例 2:
输入: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
输出: 3
约束条件
1 <= wordsDict.length <= 3 * 10^41 <= wordsDict[i].length, word1.length, word2.length <= 10wordsDict[i],word1, 和word2只包含小写英文字母word1和word2在wordsDict中都出现至少一次
解题思路
这个问题是 LeetCode 243 “最短单词距离” 的进一步扩展版本。主要区别在于，本题允许 word1 和 word2 是相同的单词。当两个单词相同时，我们需要找到同一个单词的两个不同出现位置之间的最短距离。
方法一：双指针法
我们可以修改之前的一次遍历方法，特别处理 word1 和 word2 相同的情况：
-
如果
word1和word2不同，使用与 LeetCode 243 相同的方法：- 遍历数组，记录两个单词最后出现的位置
- 当找到一个单词时，计算与另一个单词最后位置的距离
-
如果
word1和word2相同，我们需要找到同一个单词的两个连续出现位置之间的最短距离：- 记录单词最后两次出现的位置
- 计算这两个位置之间的距离
方法二：使用位置数组
另一种方法是分别收集 word1 和 word2 出现的所有位置，然后计算它们之间的最短距离：
- 遍历数组，分别记录
word1和word2的所有出现位置 - 如果
word1和word2不同，比较两个位置数组中每对位置之间的距离 - 如果
word1和word2相同，比较位置数组中相邻位置之间的距离
代码实现
方法一：双指针法
C#实现
public class Solution {public int ShortestWordDistance(string[] wordsDict, string word1, string word2) {int minDistance = int.MaxValue;int index1 = -1, index2 = -1;bool isSameWord = word1.Equals(word2);for (int i = 0; i < wordsDict.Length; i++) {if (wordsDict[i].Equals(word1)) {if (isSameWord) {// 如果是相同的单词，当前位置与上一个位置比较if (index1 != -1) {minDistance = Math.Min(minDistance, i - index1);}index1 = i;} else {index1 = i;// 如果已经找到word2，计算距离if (index2 != -1) {minDistance = Math.Min(minDistance, Math.Abs(index1 - index2));}}} else if (!isSameWord && wordsDict[i].Equals(word2)) {index2 = i;// 如果已经找到word1，计算距离if (index1 != -1) {minDistance = Math.Min(minDistance, Math.Abs(index1 - index2));}}}return minDistance;}
}
Python实现
class Solution:def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:min_distance = float('inf')index1 = index2 = -1is_same_word = word1 == word2for i, word in enumerate(wordsDict):if word == word1:if is_same_word:# 如果是相同的单词，当前位置与上一个位置比较if index1 != -1:min_distance = min(min_distance, i - index1)index1 = ielse:index1 = i# 如果已经找到word2，计算距离if index2 != -1:min_distance = min(min_distance, abs(index1 - index2))elif not is_same_word and word == word2:index2 = i# 如果已经找到word1，计算距离if index1 != -1:min_distance = min(min_distance, abs(index1 - index2))return min_distance
C++实现
class Solution {
public:int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {int minDistance = INT_MAX;int index1 = -1, index2 = -1;bool isSameWord = (word1 == word2);for (int i = 0; i < wordsDict.size(); i++) {if (wordsDict[i] == word1) {if (isSameWord) {// 如果是相同的单词，当前位置与上一个位置比较if (index1 != -1) {minDistance = min(minDistance, i - index1);}index1 = i;} else {index1 = i;// 如果已经找到word2，计算距离if (index2 != -1) {minDistance = min(minDistance, abs(index1 - index2));}}} else if (!isSameWord && wordsDict[i] == word2) {index2 = i;// 如果已经找到word1，计算距离if (index1 != -1) {minDistance = min(minDistance, abs(index1 - index2));}}}return minDistance;}
};
方法二：使用位置数组
C#实现
public class Solution {public int ShortestWordDistance(string[] wordsDict, string word1, string word2) {List<int> positions1 = new List<int>();List<int> positions2 = new List<int>();// 收集位置for (int i = 0; i < wordsDict.Length; i++) {if (wordsDict[i].Equals(word1)) {positions1.Add(i);}if (wordsDict[i].Equals(word2)) {positions2.Add(i);}}// 如果单词相同，positions1和positions2包含相同的位置if (word1.Equals(word2)) {int minDist = int.MaxValue;// 计算相邻位置之间的最小距离for (int i = 1; i < positions1.Count; i++) {minDist = Math.Min(minDist, positions1[i] - positions1[i - 1]);}return minDist;} else {// 计算两个位置数组之间的最小距离int minDist = int.MaxValue;int i = 0, j = 0;while (i < positions1.Count && j < positions2.Count) {minDist = Math.Min(minDist, Math.Abs(positions1[i] - positions2[j]));// 移动指向较小位置的指针if (positions1[i] < positions2[j]) {i++;} else {j++;}}return minDist;}}
}
Python实现
class Solution:def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:positions1 = [i for i, word in enumerate(wordsDict) if word == word1]positions2 = [i for i, word in enumerate(wordsDict) if word == word2]# 如果单词相同，计算相邻位置之间的最小距离if word1 == word2:return min(positions1[i] - positions1[i-1] for i in range(1, len(positions1)))# 使用双指针计算两个位置数组之间的最小距离i = j = 0min_distance = float('inf')while i < len(positions1) and j < len(positions2):min_distance = min(min_distance, abs(positions1[i] - positions2[j]))if positions1[i] < positions2[j]:i += 1else:j += 1return min_distance
C++实现
class Solution {
public:int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {vector<int> positions1;vector<int> positions2;// 收集位置for (int i = 0; i < wordsDict.size(); i++) {if (wordsDict[i] == word1) {positions1.push_back(i);}if (wordsDict[i] == word2) {positions2.push_back(i);}}// 如果单词相同，positions1和positions2包含相同的位置if (word1 == word2) {int minDist = INT_MAX;// 计算相邻位置之间的最小距离for (int i = 1; i < positions1.size(); i++) {minDist = min(minDist, positions1[i] - positions1[i - 1]);}return minDist;} else {// 计算两个位置数组之间的最小距离int minDist = INT_MAX;int i = 0, j = 0;while (i < positions1.size() && j < positions2.size()) {minDist = min(minDist, abs(positions1[i] - positions2[j]));// 移动指向较小位置的指针if (positions1[i] < positions2[j]) {i++;} else {j++;}}return minDist;}}
};
性能分析
方法一：双指针法
- 时间复杂度：O(n)，其中 n 是
wordsDict的长度。我们只需遍历数组一次。 - 空间复杂度：O(1)，只需要几个变量来存储位置和最短距离。
方法二：使用位置数组
- 时间复杂度：O(n)，其中 n 是
wordsDict的长度。虽然我们需要遍历数组来收集位置，但后续的双指针比较只需 O(m+k) 时间，其中 m 和 k 是两个单词出现的次数。总体复杂度仍为 O(n)。 - 空间复杂度：O(m+k)，其中 m 和 k 是两个单词出现的次数。我们需要存储每个单词的所有位置。
方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 优势 | 劣势 |
|---|---|---|---|---|
| 双指针法 | O(n) | O(1) | 空间占用少 | 实现稍复杂 |
| 位置数组 | O(n) | O(m+k) | 实现清晰 | 空间占用较大 |
方法优化
对于方法一，我们可以进一步优化代码结构，使其更简洁、更易理解：
def shortestWordDistance(wordsDict, word1, word2):min_distance = float('inf')last_pos = -1for i, word in enumerate(wordsDict):if word == word1 or word == word2:# 如果找到目标单词if last_pos != -1 and (word1 == word2 or word != wordsDict[last_pos]):# 如果是相同单词，或者与上一个找到的单词不同min_distance = min(min_distance, i - last_pos)last_pos = ireturn min_distance
这个优化版本统一处理了相同和不同单词的情况，代码更加简洁明了。
常见错误与陷阱
- 忽略相同单词的特殊处理：当
word1和word2相同时，需要特别处理。不能简单地比较每对位置，而应该比较相邻位置。 - 在位置数组方法中没有正确处理相同单词：当单词相同时，positions1 和 positions2 包含相同的位置，不能直接使用双指针比较。
- 数组越界：在计算相邻位置距离时，需要确保数组中至少有两个元素。
相关题目
- LeetCode 第243题：最短单词距离
- LeetCode 第244题：最短单词距离 II
- LeetCode 第246题：中心对称数