力扣（LeetCode）243. 最短单词距离（2022.08.31）

请设计一个类，使该类的构造函数能够接收一个字符串数组。然后再实现一个方法，该方法能够分别接收两个单词，并返回列表中这两个单词之间的最短距离。

实现 WordDistanc 类:

WordDistance(String[] wordsDict) 用字符串数组 wordsDict 初始化对象。
int shortest(String word1, String word2) 返回数组 worddict 中 word1 和 word2 之间的最短距离。

示例 1:

输入:
[“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⁴
1 <= wordsDict[i].length <= 10
wordsDict[i] 由小写英文字母组成
word1 和 word2 在数组 wordsDict 中
word1 != word2
shortest 操作次数不大于 5000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shortest-word-distance-ii

方法一：哈希表+双指针

C++提交内容：

class WordDistance {
public:
    WordDistance(vector<string>& wordsDict) {
        int length = wordsDict.size();
        for (int i = 0; i < length; i++) {
            string word = wordsDict[i];
            indicesMap[word].emplace_back(i);
        }
    }
    
    int shortest(string word1, string word2) {
        vector<int> indices1 = indicesMap[word1];
        vector<int> indices2 = indicesMap[word2];
        int size1 = indices1.size(), size2 = indices2.size();
        int pos1 = 0, pos2 = 0;
        int ans = INT_MAX;
        while (pos1 < size1 && pos2 < size2) {
            int index1 = indices1[pos1], index2 = indices2[pos2];
            ans = min(ans, abs(index1 - index2));
            if (index1 < index2) {
                pos1++;
            } else {
                pos2++;
            }
        }
        return ans;
    }
private:
    unordered_map<string, vector<int>> indicesMap;
};

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance* obj = new WordDistance(wordsDict);
 * int param_1 = obj->shortest(word1,word2);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36