Shortest Word Distance Ii - Leetcode Solution

The problem Shortest Word Distance II on LeetCode asks us to implement a class WordDistance that will be used to find the shortest distance between two given words in a list of words.

The key idea behind this problem is to preprocess the list of words and store their indices in a hash table. This will allow us to quickly look up the indices of the given words and calculate the shortest distance between them.

To solve this problem, we can follow the following steps:

1. Implement a constructor method for the WordDistance class that will take in a list of words and preprocess it by storing the indices of each word in a hash table.

2. Implement a method shortest(word1, word2) that will take in two words and return the shortest distance between them.

3. In the shortest() method, retrieve the indices of both words from the hash table.

4. Initialize two pointers, one pointing to the index of word1 and the other pointing to the index of word2.

5. Keep track of the minimum distance between the two pointers as we iterate through the indices of both words.

6. Return the minimum distance at the end.

Here's the Python code:

class WordDistance:
    def __init__(self, words: List[str]):
        self.word_indices = {}
        for i, w in enumerate(words):
            if w in self.word_indices:
                self.word_indices[w].append(i)
            else:
                self.word_indices[w] = [i]
        
    def shortest(self, word1: str, word2: str) -> int:
        i = 0
        j = 0
        min_distance = float('inf')
        while i < len(self.word_indices[word1]) and j < len(self.word_indices[word2]):
            min_distance = min(min_distance, abs(self.word_indices[word1][i] - self.word_indices[word2][j]))
            if self.word_indices[word1][i] < self.word_indices[word2][j]:
                i += 1
            else:
                j += 1
        return min_distance

The time complexity of this solution is O(n) for preprocessing the list of words and O(m + n) for each query, where m and n are the lengths of the indices lists for the two given words. The space complexity is also O(n) for storing the hash table of indices.

1