Shortest Word Distance II

To design a data structure that efficiently answers queries about the shortest distance between two different strings from an array, you can precompute the indices of each word and store them in a dictionary during the initialization. Then, you can use this dictionary to quickly find the shortest distance between two given words.

Here’s the step-by-step implementation:

1. Initialization: During initialization, store the indices of each word in a dictionary. The keys of the dictionary are the words, and the values are lists of indices where those words occur in the array.
2. Finding Shortest Distance: To find the shortest distance between two words, you can iterate through their lists of indices and find the minimum difference between any pair of indices, one from each list.

Here’s the Python code implementing the WordDistance class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class WordDistance:

    def __init__(self, wordsDict: List[str]):
        self.word_indices = collections.defaultdict(list)
        for idx, word in enumerate(wordsDict):
            self.word_indices[word].append(idx)

    def shortest(self, word1: str, word2: str) -> int:
        indices1 = self.word_indices[word1]
        indices2 = self.word_indices[word2]
        i, j = 0, 0
        min_distance = float('inf')

        while i < len(indices1) and j < len(indices2):
            index1, index2 = indices1[i], indices2[j]
            min_distance = min(min_distance, abs(index1 - index2))

            if index1 < index2:
                i += 1
            else:
                j += 1

        return min_distance

Here, we store the indices for each word in self.word_indices. In the shortest method, we compare the indices of word1 and word2 and find the minimum difference between them.

The time complexity for the initialization is O(n), where n is the total number of words in the array. The time complexity for the shortest method is O(m + k), where m and k are the occurrences of word1 and word2, respectively. The space complexity is O(n).