244. Shortest Word Distance II

Posted on Edited on In

244. Shortest Word Distance II

Description

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

  • WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict.
  • int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input

["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output

[null, 3, 1]

Explanation

WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

Constraints:

  • 1 <= wordsDict.length <= 3 * 10^4
  • 1 <= wordsDict[i].length <= 10
  • wordsDict[i] consists of lowercase English letters.
  • word1 and word2 are in wordsDict.
  • word1 != word2
  • At most 5000 calls will be made to shortest.

Hints/Notes

Solution

Language: C++

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
class WordDistance {
public:
    unordered_map<string, vector<int>> wordToIndexes;
    WordDistance(vector<string>& wordsDict) {
        int n = wordsDict.size();
        for (int i = 0; i < n; i++) {
            wordToIndexes[wordsDict[i]].push_back(i);
        }
    }

    int shortest(string word1, string word2) {
        auto v1 = wordToIndexes[word1];
        auto v2 = wordToIndexes[word2];
        int idx1 = 0, idx2 = 0, n1 = v1.size(), n2 = v2.size();
        int res = INT_MAX;
        while (idx1 < n1 && idx2 < n2) {
            res = min(res, abs(v1[idx1] - v2[idx2]));
            if (v1[idx1] < v2[idx2]) {
                idx1++;
            } else {
                idx2++;
            }
        }
        return res;
    }
};

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance* obj = new WordDistance(wordsDict);
 * int param_1 = obj->shortest(word1,word2);
 */