Solution: Shortest Word Distance II

Statement

Design a data structure that takes in an array of strings and efficiently computes the shortest distance between any two different strings in the array.

Implement the WordDistance class:

• WordDistance(String[] wordsDict): Initializes the object with an array of strings.

• int shortest(String word1, String word2): Returns the shortest distance between word1 and word2 in the array of strings.

Constraints:

• $1 \leq$ wordsDict.length $\leq10^3$

• $1 \leq$ wordsDict[i].length $\leq 10$

• wordsDict[i] consists of lowercase English letters

• word1 and word2 are in wordsDict

• word1 != word2

• At most, $1000$ calls will be made to the shortest

Solution

The algorithm uses a custom data structure to efficiently calculate the shortest distance between words in an array. It starts by creating a dictionary that records the positions of each word in the input array, allowing for quick retrieval of word locations. When processing a query, the algorithm employs two pointers to compare the positions of the words. The pointer with the smaller index is always advanced, potentially bringing it closer to the other word and reducing the distance between the two positions. This approach ensures that all possible pairs of positions are considered, accurately calculating the shortest distance. The combination of preprocessing and smart traversal makes this algorithm an efficient solution for word distance queries.

Constructor

1. The WordDistance class uses a dictionary to store the indexes of each word in the given wordsDict array. This dictionary, wordIndices, maps each word to a list of its positions (indexes) in the array.

2. The Constructor method iterates over the wordsDict array, which provides both the index and the word at that index. For each word, it appends the index to the corresponding list in the wordIndices dictionary.

The query for the shortest distance

1. The shortest method retrieves the lists of indexes for the two input words (word1 and word2) from the wordIndices dictionary.

2. It initializes two pointers, i and j, to traverse the lists of indexes (indices1 and indices2). It also initializes minDistance to infinity, holding the minimum distance found.

3. The algorithm uses a two-pointer technique to find the minimum distance:

   1. It compares the current elements pointed to by i and j in the two lists (indices1[i] and indices2[j]).

   2. It updates min_distance to be the smaller of the current minDistance and the absolute difference between indices1[i] and indices2[j].

   3. It moves the pointer that points to the smaller index value. This helps to gradually minimize the difference between the two indexes.

4. The loop continues until one of the lists is fully traversed. At this point, minDistance will hold the smallest distance between the positions of the two words.

Let’s look at the following illustration to get a better understanding of the solution: