Domain 1EasyCORE

Shortest Word Distance

The problem requires finding the shortest distance between two distinct words in an array of strings. The inputs are: - `wordsDict`: An array of strings where each string consists of lowercase English letters. - `word1` and `word2`: Two different strings that exist in `wordsDict`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

243. Shortest Word Distance

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 62.1%


Problem Breakdown

The problem requires finding the shortest distance between two distinct words in an array of strings. The inputs are:

  • wordsDict: An array of strings where each string consists of lowercase English letters.
  • word1 and word2: Two different strings that exist in wordsDict.

The output is an integer representing the minimum number of steps between the occurrences of word1 and word2 in wordsDict. The constraints ensure that word1 and word2 are distinct and present in the array.

Intuition

A brute-force approach would involve checking every pair of indices where word1 and word2 occur, calculating the distance between them, and keeping track of the minimum distance. This approach has a time complexity of O(n^2), which is inefficient for large arrays.

The key insight is to traverse the array once while maintaining the most recent positions of word1 and word2. By updating these positions as we encounter either word, we can calculate the distance between them immediately and update the minimum distance accordingly. This reduces the time complexity to O(n).

Approach

  1. Initialize variables to store the most recent indices of word1 and word2, both set to -1 initially.
  2. Initialize a variable min_distance to a large number (e.g., infinity) to keep track of the minimum distance found.
  3. Iterate through the array wordsDict:
    • If the current word matches word1, update its index and calculate the distance from the most recent occurrence of word2. Update min_distance if this new distance is smaller.
    • If the current word matches word2, update its index and calculate the distance from the most recent occurrence of word1. Update min_distance if this new distance is smaller.
  4. After iterating through the array, return min_distance.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of wordsDict. We traverse the array once.
  • Space Complexity: O(1). We use a constant amount of extra space for variables.

Solution

def shortestDistance(wordsDict, word1, word2):
    index1 = -1
    index2 = -1
    min_distance = float('inf')
    
    for i in range(len(wordsDict)):
        if wordsDict[i] == word1:
            index1 = i
            if index2 != -1:
                min_distance = min(min_distance, abs(index1 - index2))
        elif wordsDict[i] == word2:
            index2 = i
            if index1 != -1:
                min_distance = min(min_distance, abs(index1 - index2))
    
    return min_distance

Edge Cases Handled

  • The array contains only one occurrence of either word1 or word2. In this case, the distance will be calculated correctly as we update indices and distances only when both words are found.
  • The array is very large (up to 30,000 elements). The linear time complexity ensures that the solution remains efficient even for large inputs.