Shortest Word Distance III

The problem is about finding the shortest distance between two words in a list of words. Here is the Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        index1, index2 = float('-inf'), float('-inf')
        min_distance = float('inf')
        same = True if word1 == word2 else False

        for i, word in enumerate(wordsDict):
            if word == word1:
                if same:
                    index2 = index1
                index1 = i
            elif word == word2:
                index2 = i

            min_distance = min(min_distance, abs(index1 - index2))

        return min_distance

In this solution, we use two pointers: index1 and index2 to store the most recent locations of word1 and word2.

We iterate through wordsDict, and when we encounter word1 or word2, we update the corresponding index.

In case word1 and word2 are the same, we need to handle this situation differently. We always update index2 to the last seen index before updating index1 again. This ensures we don’t calculate the distance between the word and itself.

We keep track of the min_distance in the loop. After scanning all words, we return min_distance, which represents the shortest distance between word1 and word2.

The task is to find the shortest distance between two given words, word1 and word2, in a list of words wordsDict. The words may or may not be different. The solution will involve iterating through the list and tracking the last seen indices of the two words.

Here’s a step-by-step approach:

1. Initialize two variables to store the last seen indices of word1 and word2. Set them to negative values initially, as they are not seen yet.
2. Initialize a variable to store the minimum distance and set it to a large number.
3. Iterate through the list, and if the current word is equal to either word1 or word2, update the corresponding last seen index and calculate the distance.
4. If word1 and word2 are the same, take care to handle the case where the current word is equal to both word1 and word2.

Here’s the code:

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

class Solution:
    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        index1, index2 = -1, -1
        min_distance = float('inf')

        for i, word in enumerate(wordsDict):
            if word1 == word2 and word == word1:
                if index1 >= 0:
                    min_distance = min(min_distance, i - index1)
                index1 = i
            else:
                if word == word1:
                    index1 = i
                if word == word2:
                    index2 = i
                if index1 >= 0 and index2 >= 0:
                    min_distance = min(min_distance, abs(index1 - index2))

        return min_distance

The code first checks if word1 is the same as word2 and handles that special case. Otherwise, it simply updates the last seen indices for word1 and word2 and calculates the minimum distance.

The time complexity of this function is O(n), where n is the number of words in wordsDict. The space complexity is O(1), as we are only using a constant amount of extra space.