Shortest Word Distance

Difficulty: Easy | Acceptance: N/A | Paid: No Topics: Array, String

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

You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

• Examples
• Constraints
• Brute Force
• One Pass

Examples

Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3
Explanation: "coding" is at index 3 and "practice" is at index 0. The distance is |3 - 0| = 3.

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1
Explanation: "makes" appears at index 1 and 4. "coding" is at index 3. The shortest distance is |3 - 4| = 1.

Constraints

1 <= wordsDict.length <= 3 * 10⁴
1 <= wordsDict[i].length <= 10
wordsDict[i] consists of lowercase English letters.
word1 and word2 are in wordsDict.
word1 != word2.

Brute Force

Intuition Check every occurrence of word1 against every occurrence of word2 to find the minimum absolute difference in their indices.

Steps

• Initialize min_dist to a large value.
• Iterate through the array with index i.
• If wordsDict[i] matches word1, iterate through the array again with index j.
• If wordsDict[j] matches word2, update min_dist with the minimum of current min_dist and abs(i - j).
• Return min_dist.

class Solution:
    def shortestDistance(self, wordsDict: list[str], word1: str, word2: str) -> int:
        min_dist = float('inf')
        n = len(wordsDict)
        for i in range(n):
            if wordsDict[i] == word1:
                for j in range(n):
                    if wordsDict[j] == word2:
                        min_dist = min(min_dist, abs(i - j))
        return min_dist

Complexity

• Time: O(N²) where N is the length of wordsDict.
• Space: O(1)
• Notes: Simple but inefficient for large inputs.

One Pass

Intuition Traverse the list once, keeping track of the most recent indices where word1 and word2 were seen. Calculate the distance whenever both indices are valid.

Steps

• Initialize index1 and index2 to -1.
• Initialize min_dist to a large value.
• Iterate through the array with index i.
• If wordsDict[i] is word1, update index1.
• If wordsDict[i] is word2, update index2.
• If both index1 and index2 are not -1, update min_dist with min(min_dist, abs(index1 - index2)).
• Return min_dist.

class Solution:
    def shortestDistance(self, wordsDict: list[str], word1: str, word2: str) -> int:
        i1 = -1
        i2 = -1
        min_dist = float('inf')
        for i, word in enumerate(wordsDict):
            if word == word1:
                i1 = i
            elif word == word2:
                i2 = i
            
            if i1 != -1 and i2 != -1:
                min_dist = min(min_dist, abs(i1 - i2))
        return min_dist

Complexity

• Time: O(N) where N is the length of wordsDict.
• Space: O(1)
• Notes: Optimal solution with linear time complexity.