江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode第243题：最短单词距离

LeetCode第243题：最短单词距离

问题描述

给定一个单词数组 wordsDict 和两个单词 word1 和 word2，返回这两个单词在数组中出现的最短距离。

注意：word1 和 word2 是不同的单词，且它们都在 wordsDict 中。

难度：简单

示例

示例 1:

输入: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
输出: 3

示例 2:

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

约束条件

  • 1 <= wordsDict.length <= 3 * 10^4
  • 1 <= wordsDict[i].length <= 10
  • wordsDict[i] 由小写英文字母组成
  • word1 和 word2 是在 wordsDict 中不同的单词
  • word1 和 word2 不是同一个单词

解题思路

要找到两个单词在数组中出现的最短距离，我们需要遍历数组，记录每个单词出现的位置，然后计算这些位置之间的最短距离。

方法一：暴力法

  1. 遍历数组，记录下 word1 和 word2 在数组中出现的所有位置
  2. 计算 word1 每个位置与 word2 每个位置之间的距离，取最小值

方法二：一次遍历

更高效的方法是在遍历数组的同时，记录 word1 和 word2 最近一次出现的位置，然后实时更新最短距离：

  1. 初始化 word1 和 word2 的位置为 -1（表示还未找到）
  2. 遍历数组，当找到 word1 或 word2 时，更新对应的位置
  3. 如果 word1 和 word2 都已找到，计算它们当前位置之间的距离，并更新最短距离
  4. 继续遍历，直到数组结束

这个方法的优点是只需要遍历一次数组，并且不需要额外的空间来存储所有位置。

代码实现

方法一：暴力法

C#实现

public class Solution {
    public int ShortestDistance(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] == word1) {
                positions1.Add(i);
            } else if (wordsDict[i] == word2) {
                positions2.Add(i);
            }
        }
        
        // 计算最短距离
        int minDistance = int.MaxValue;
        foreach (int pos1 in positions1) {
            foreach (int pos2 in positions2) {
                minDistance = Math.Min(minDistance, Math.Abs(pos1 - pos2));
            }
        }
        
        return minDistance;
    }
}

Python实现

class Solution:
    def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        positions1 = []
        positions2 = []
        
        # 记录两个单词的所有位置
        for i, word in enumerate(wordsDict):
            if word == word1:
                positions1.append(i)
            elif word == word2:
                positions2.append(i)
        
        # 计算最短距离
        min_distance = float('inf')
        for pos1 in positions1:
            for pos2 in positions2:
                min_distance = min(min_distance, abs(pos1 - pos2))
        
        return min_distance

C++实现

class Solution {
public:
    int shortestDistance(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);
            } else if (wordsDict[i] == word2) {
                positions2.push_back(i);
            }
        }
        
        // 计算最短距离
        int minDistance = INT_MAX;
        for (int pos1 : positions1) {
            for (int pos2 : positions2) {
                minDistance = min(minDistance, abs(pos1 - pos2));
            }
        }
        
        return minDistance;
    }
};

方法二：一次遍历

C#实现

public class Solution {
    public int ShortestDistance(string[] wordsDict, string word1, string word2) {
        int pos1 = -1;
        int pos2 = -1;
        int minDistance = int.MaxValue;
        
        for (int i = 0; i < wordsDict.Length; i++) {
            if (wordsDict[i] == word1) {
                pos1 = i;
            } else if (wordsDict[i] == word2) {
                pos2 = i;
            }
            
            // 当两个单词都找到时，计算距离
            if (pos1 != -1 && pos2 != -1) {
                minDistance = Math.Min(minDistance, Math.Abs(pos1 - pos2));
            }
        }
        
        return minDistance;
    }
}

Python实现

class Solution:
    def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        pos1 = pos2 = -1
        min_distance = float('inf')
        
        for i, word in enumerate(wordsDict):
            if word == word1:
                pos1 = i
            elif word == word2:
                pos2 = i
            
            # 当两个单词都找到时，计算距离
            if pos1 != -1 and pos2 != -1:
                min_distance = min(min_distance, abs(pos1 - pos2))
        
        return min_distance

C++实现

class Solution {
public:
    int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
        int pos1 = -1;
        int pos2 = -1;
        int minDistance = INT_MAX;
        
        for (int i = 0; i < wordsDict.size(); i++) {
            if (wordsDict[i] == word1) {
                pos1 = i;
            } else if (wordsDict[i] == word2) {
                pos2 = i;
            }
            
            // 当两个单词都找到时，计算距离
            if (pos1 != -1 && pos2 != -1) {
                minDistance = min(minDistance, abs(pos1 - pos2));
            }
        }
        
        return minDistance;
    }
};

性能分析

方法一：暴力法

  • 时间复杂度：O(n * m1 * m2)，其中 n 是数组长度，m1 和 m2 分别是 word1 和 word2 在数组中出现的次数。
  • 空间复杂度：O(m1 + m2)，用于存储两个单词的所有位置。

方法二：一次遍历

  • 时间复杂度：O(n)，其中 n 是数组长度。我们只需遍历一次数组。
  • 空间复杂度：O(1)，只需要几个变量来存储位置和最短距离。

方法对比

方法 时间复杂度 空间复杂度 优势 劣势
暴力法 O(n * m1 * m2) O(m1 + m2) 实现直观 当单词出现频率高时效率低
一次遍历 O(n) O(1) 效率高，空间占用少 无明显劣势

常见错误与陷阱

  1. 忘记初始化位置：在方法二中，应该将初始位置设为 -1，表示还未找到单词。
  2. 只有当两个位置都有效时才计算距离：确保 pos1 和 pos2 都不为 -1 时才计算距离。
  3. 忽略了单词顺序：word1 可能在 word2 之后出现，要考虑所有可能的相对位置。

相关题目