LeetCode第244题_最短单词距离II

LeetCode第244题：最短单词距离II

问题描述

设计一个类，接收一个单词数组 wordsDict，并实现一个方法，该方法能够计算两个不同单词在该数组中出现位置的最短距离。

你需要实现一个 WordDistance 类:

• WordDistance(String[] wordsDict) 初始化对象，用单词数组 wordsDict 初始化对象。
• int shortest(String word1, String word2) 返回数组 wordsDict 中两个单词 word1 和 word2 的最短距离。

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

难度：中等

示例

输入: 
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
输出: [null, 3, 1]解释:
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // 返回 3
wordDistance.shortest("makes", "coding");    // 返回 1

约束条件

• 1 <= wordsDict.length <= 3 * 10^4
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] 由小写英文字母组成
• word1 和 word2 在 wordsDict 中，且它们是不同的单词
• shortest 操作次数不超过 5000

解题思路

这个问题是 LeetCode 243 “最短单词距离” 的进阶版本。主要区别在于，本题需要设计一个类，可以重复查询不同单词对之间的最短距离。关键在于如何有效地预处理数据，以便快速响应查询请求。

我们可以采用以下两种主要方法：

方法一：预处理位置索引

这种方法在初始化时，将每个单词在数组中的所有位置存储在一个哈希表中：

1. 构造函数中，遍历单词数组 wordsDict，记录每个单词出现的所有位置
2. 对于 shortest 方法，获取两个单词的位置列表，然后计算它们之间的最短距离
3. 为了计算最短距离，我们比较两个位置列表中的每对位置，找到最小的绝对差值

方法二：双指针优化

方法一在计算最短距离时可能会做很多不必要的比较。考虑到位置列表是有序的（因为我们按顺序遍历数组），我们可以使用双指针方法优化距离计算：

1. 初始化两个指针，分别指向两个位置列表的开始
2. 比较当前两个指针指向的位置，计算它们的距离
3. 移动指向较小位置的指针
4. 重复步骤 2 和 3，直到其中一个指针到达列表末尾
5. 返回在此过程中找到的最小距离

这种方法避免了不必要的比较，复杂度从 O(m*n) 降低到 O(m+n)，其中 m 和 n 是两个单词在数组中出现的次数。

代码实现

方法一：预处理位置索引

C#实现

public class WordDistance {private Dictionary<string, List<int>> wordToIndices;public WordDistance(string[] wordsDict) {wordToIndices = new Dictionary<string, List<int>>();// 预处理每个单词的位置for (int i = 0; i < wordsDict.Length; i++) {if (!wordToIndices.ContainsKey(wordsDict[i])) {wordToIndices[wordsDict[i]] = new List<int>();}wordToIndices[wordsDict[i]].Add(i);}}public int Shortest(string word1, string word2) {List<int> indices1 = wordToIndices[word1];List<int> indices2 = wordToIndices[word2];int minDistance = int.MaxValue;// 计算两个位置列表中的最短距离foreach (int idx1 in indices1) {foreach (int idx2 in indices2) {minDistance = Math.Min(minDistance, Math.Abs(idx1 - idx2));}}return minDistance;}
}

Python实现

class WordDistance:def __init__(self, wordsDict: List[str]):self.locations = {}# 预处理每个单词的位置for i, word in enumerate(wordsDict):if word not in self.locations:self.locations[word] = []self.locations[word].append(i)def shortest(self, word1: str, word2: str) -> int:locations1 = self.locations[word1]locations2 = self.locations[word2]min_dist = float('inf')# 计算两个位置列表中的最短距离for loc1 in locations1:for loc2 in locations2:min_dist = min(min_dist, abs(loc1 - loc2))return min_dist

C++实现

class WordDistance {
private:unordered_map<string, vector<int>> wordToIndices;public:WordDistance(vector<string>& wordsDict) {// 预处理每个单词的位置for (int i = 0; i < wordsDict.size(); i++) {wordToIndices[wordsDict[i]].push_back(i);}}int shortest(string word1, string word2) {vector<int>& indices1 = wordToIndices[word1];vector<int>& indices2 = wordToIndices[word2];int minDistance = INT_MAX;// 计算两个位置列表中的最短距离for (int idx1 : indices1) {for (int idx2 : indices2) {minDistance = min(minDistance, abs(idx1 - idx2));}}return minDistance;}
};

方法二：双指针优化

C#实现

public class WordDistance {private Dictionary<string, List<int>> wordToIndices;public WordDistance(string[] wordsDict) {wordToIndices = new Dictionary<string, List<int>>();// 预处理每个单词的位置for (int i = 0; i < wordsDict.Length; i++) {if (!wordToIndices.ContainsKey(wordsDict[i])) {wordToIndices[wordsDict[i]] = new List<int>();}wordToIndices[wordsDict[i]].Add(i);}}public int Shortest(string word1, string word2) {List<int> indices1 = wordToIndices[word1];List<int> indices2 = wordToIndices[word2];int i = 0, j = 0;int minDistance = int.MaxValue;// 使用双指针计算最短距离while (i < indices1.Count && j < indices2.Count) {int idx1 = indices1[i];int idx2 = indices2[j];minDistance = Math.Min(minDistance, Math.Abs(idx1 - idx2));// 移动指向较小位置的指针if (idx1 < idx2) {i++;} else {j++;}}return minDistance;}
}

Python实现

class WordDistance:def __init__(self, wordsDict: List[str]):self.locations = {}# 预处理每个单词的位置for i, word in enumerate(wordsDict):if word not in self.locations:self.locations[word] = []self.locations[word].append(i)def shortest(self, word1: str, word2: str) -> int:locations1 = self.locations[word1]locations2 = self.locations[word2]i, j = 0, 0min_dist = float('inf')# 使用双指针计算最短距离while i < len(locations1) and j < len(locations2):min_dist = min(min_dist, abs(locations1[i] - locations2[j]))# 移动指向较小位置的指针if locations1[i] < locations2[j]:i += 1else:j += 1return min_dist

C++实现

class WordDistance {
private:unordered_map<string, vector<int>> wordToIndices;public:WordDistance(vector<string>& wordsDict) {// 预处理每个单词的位置for (int i = 0; i < wordsDict.size(); i++) {wordToIndices[wordsDict[i]].push_back(i);}}int shortest(string word1, string word2) {vector<int>& indices1 = wordToIndices[word1];vector<int>& indices2 = wordToIndices[word2];int i = 0, j = 0;int minDistance = INT_MAX;// 使用双指针计算最短距离while (i < indices1.size() && j < indices2.size()) {int idx1 = indices1[i];int idx2 = indices2[j];minDistance = min(minDistance, abs(idx1 - idx2));// 移动指向较小位置的指针if (idx1 < idx2) {i++;} else {j++;}}return minDistance;}
};

性能分析

方法一：预处理位置索引

• 初始化时间复杂度：O(n)，其中 n 是 wordsDict 的长度。我们需要遍历整个数组一次来建立索引。
• 查询时间复杂度：O(m * k)，其中 m 和 k 分别是 word1 和 word2 在数组中出现的次数。在最坏情况下，我们需要比较每对位置。
• 空间复杂度：O(n)，用于存储所有单词的位置索引。

方法二：双指针优化

• 初始化时间复杂度：O(n)，与方法一相同。
• 查询时间复杂度：O(m + k)，其中 m 和 k 分别是 word1 和 word2 在数组中出现的次数。使用双指针方法，我们只需遍历两个位置列表一次。
• 空间复杂度：O(n)，与方法一相同。

方法对比

方法	初始化时间	查询时间	空间复杂度	优势	劣势
预处理位置索引	O(n)	O(m * k)	O(n)	实现简单直观	查询效率较低
双指针优化	O(n)	O(m + k)	O(n)	查询效率高	无明显劣势

设计思路分析

1. 空间与时间权衡：该设计在初始化时预先计算并存储所有单词的位置，牺牲一些空间来换取更快的查询速度。这适用于查询次数远多于单词数量的情况。

2. 双指针技巧：利用位置列表的有序性，通过双指针算法将查询复杂度从 O(m*k) 降低到 O(m+k)，显著提高了查询效率。

3. 哈希表索引：使用哈希表按单词索引位置列表，实现了 O(1) 时间的位置列表查找。

相关题目

• LeetCode 第243题：最短单词距离
• LeetCode 第245题：最短单词距离 III
• LeetCode 第249题：移位字符串分组