Shortest Word Distance

One way to approach this problem is by iterating over the words in the list and tracking the most recent locations of word1 and word2. Whenever we find an occurrence of either word, we calculate the distance to the most recent occurrence of the other word and update our result if the calculated distance is less than our current result.

Here is the Python code:

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

class Solution:
    def shortestDistance(self, wordsDict: list, word1: str, word2: str) -> int:
        index1, index2 = -1, -1
        min_distance = len(wordsDict)

        for i, word in enumerate(wordsDict):
            if word == word1:
                index1 = i
                if index2 != -1:
                    min_distance = min(min_distance, index1 - index2)
            elif word == word2:
                index2 = i
                if index1 != -1:
                    min_distance = min(min_distance, index2 - index1)

        return min_distance

In this code, we iterate over each word in the list. If the word is word1, we update index1 and calculate the distance to the most recent occurrence of word2, if any. If the word is word2, we update index2 and calculate the distance to the most recent occurrence of word1, if any. We keep track of the minimum distance we have seen so far and return it at the end.

The time complexity of this solution is O(n), where n is the number of words in the list, because we perform a single pass through the words. The space complexity is O(1), as we only use a few integer variables to track the most recent occurrences of word1 and word2 and the minimum distance.

Refactored code based on C++ solution in discussion:

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

class Solution:
    def shortestDistance(self, words: list, word1: str, word2: str) -> int:
        p1, p2, min_distance = -1, -1, float('inf')

        for i, word in enumerate(words):
            if word == word1:
                p1 = i
            if word == word2:
                p2 = i
            if p1 != -1 and p2 != -1:
                min_distance = min(min_distance, abs(p1 - p2))

        return min_distance

This approach leverages the technique known as “sliding window”. By maintaining pointers (p1 and p2) to the latest occurrences of word1 and word2, and updating the minimum distance as we traverse the list, we ensure that we always have the shortest distance between the latest occurrences of word1 and word2. This technique is efficient because it only requires a single pass over the data and does not require any additional space proportional to the size of the input.

Key Takeaway

The key takeaway is that the solution keeps a running min_distance seen so far. This keeps improving the result as we loop through all the words in the given dictionary.