Solution Explanation for Shortest Word Distance

This problem asks to find the shortest distance between two given words within an array of strings. The optimal approach is a single pass through the array, tracking the indices of the target words.

Approach

The solution uses a single iteration through the wordsDict array. We maintain two integer variables, i and j, to store the most recent indices of word1 and word2 respectively. Initially, both are set to -1, indicating that neither word has been encountered yet.

During each iteration:

1. Check for word1: If the current word (wordsDict[k]) is equal to word1, we update i to the current index k.
2. Check for word2: Similarly, if the current word is equal to word2, we update j to k.
3. Calculate distance: If both i and j are not -1 (meaning both words have been found at least once), we calculate the absolute difference between i and j (abs(i - j)) and update the minimum distance (ans) if this difference is smaller.

After iterating through the entire array, ans will hold the shortest distance between word1 and word2.

Time and Space Complexity Analysis

• Time Complexity: O(N), where N is the length of wordsDict. We perform a single pass through the array.
• Space Complexity: O(1). We use only a constant amount of extra space to store variables (i, j, ans).

Code Implementation in Different Languages

The provided code snippets in Python, Java, C++, and Go all implement this approach effectively. They differ slightly in syntax and library functions used for absolute value calculation and minimum finding, but the core logic remains identical.

Example (Python):

class Solution:
    def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        i = j = -1
        ans = float('inf') # Use infinity for initial minimum distance
        for k, w in enumerate(wordsDict):
            if w == word1:
                i = k
            if w == word2:
                j = k
            if i != -1 and j != -1:
                ans = min(ans, abs(i - j))
        return ans
 

The other languages utilize similar techniques: Java uses Integer.MAX_VALUE as the initial maximum distance; C++ uses INT_MAX; and Go defines a custom abs function and uses math.MaxInt32. The core algorithm remains consistent across all implementations.