LeetCode Solutions Blog

Shortest Word Distance

Number: 243

Difficulty: Easy

Paid? Yes

Problem Description

Given an array of strings wordsDict and two different strings word1 and word2 that already exist in the array, return the shortest distance between these two words in the list.

Key Insights

Perform a single pass through wordsDict.
Use two variables to track the most recent indices of word1 and word2.
Calculate the absolute difference between indices every time both words have been encountered.
Update the shortest distance seen result during the iteration.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in wordsDict. Space Complexity: O(1), since only a constant number of variables are used.

Solution

We use a one-pass approach that iterates over the list while maintaining two pointers (or indices) for word1 and word2. When either word is encountered, update its corresponding pointer. When both pointers have valid indices, compute the current distance and update the minimum distance if needed. This simple but efficient method leverages constant extra space and ensures linear time processing.

Code Solutions

Below are code solutions with line-by-line comments.

def shortestDistance(wordsDict, word1, word2):
    # Initialize indices for word1 and word2 as -1 (indicating not found yet)
    index1, index2 = -1, -1
    # Initialize the minimum distance with a large value
    min_distance = float('inf')
    
    # Loop through the entire words list
    for i, word in enumerate(wordsDict):
        # If the current word is word1, update index1 and calculate distance if word2 was seen
        if word == word1:
            index1 = i
            if index2 != -1:
                min_distance = min(min_distance, abs(index1 - index2))
        # If the current word is word2, update index2 and calculate distance if word1 was seen
        elif word == word2:
            index2 = i
            if index1 != -1:
                min_distance = min(min_distance, abs(index1 - index2))
    
    return min_distance

# Example usage:
print(shortestDistance(["practice", "makes", "perfect", "coding", "makes"], "coding", "practice"))