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^4
• 1 <= wordsDict[i].length, word1.length, word2.length <= 10
• wordsDict[i], word1, 和 word2 只包含小写英文字母
• word1 和 word2 在 wordsDict 中都出现至少一次

解题思路

这个问题是 LeetCode 243 “最短单词距离” 的进一步扩展版本。主要区别在于，本题允许 word1 和 word2 是相同的单词。当两个单词相同时，我们需要找到同一个单词的两个不同出现位置之间的最短距离。

方法一：双指针法

我们可以修改之前的一次遍历方法，特别处理 word1 和 word2 相同的情况：

1. 如果 word1 和 word2 不同，使用与 LeetCode 243 相同的方法：

   • 遍历数组，记录两个单词最后出现的位置
   • 当找到一个单词时，计算与另一个单词最后位置的距离

2. 如果 word1 和 word2 相同，我们需要找到同一个单词的两个连续出现位置之间的最短距离：

   • 记录单词最后两次出现的位置
   • 计算这两个位置之间的距离

方法二：使用位置数组

另一种方法是分别收集 word1 和 word2 出现的所有位置，然后计算它们之间的最短距离：

1. 遍历数组，分别记录 word1 和 word2 的所有出现位置
2. 如果 word1 和 word2 不同，比较两个位置数组中每对位置之间的距离
3. 如果 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 = -1
        is_same_word = word1 == word2
        
        for i, word in enumerate(wordsDict):
            if word == word1:
                if is_same_word:
                    # 如果是相同的单词，当前位置与上一个位置比较
                    if index1 != -1:
                        min_distance = min(min_distance, i - index1)
                    index1 = i
                else:
                    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 = 0
        min_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 += 1
            else:
                j += 1
                
        return 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 是两个单词出现的次数。我们需要存储每个单词的所有位置。

方法对比

方法优化

对于方法一，我们可以进一步优化代码结构，使其更简洁、更易理解：

def shortestWordDistance(wordsDict, word1, word2):
    min_distance = float('inf')
    last_pos = -1
    
    for 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 = i
    
    return min_distance

这个优化版本统一处理了相同和不同单词的情况，代码更加简洁明了。

常见错误与陷阱

1. 忽略相同单词的特殊处理：当 word1 和 word2 相同时，需要特别处理。不能简单地比较每对位置，而应该比较相邻位置。
2. 在位置数组方法中没有正确处理相同单词：当单词相同时，positions1 和 positions2 包含相同的位置，不能直接使用双指针比较。
3. 数组越界：在计算相邻位置距离时，需要确保数组中至少有两个元素。

相关题目

• LeetCode 第243题：最短单词距离
• LeetCode 第244题：最短单词距离 II
• LeetCode 第246题：中心对称数