Problem Description

The Shortest Word Distance problem asks you to find the minimum distance (in indices) between two given words in a list of words.

Given:

• A list of strings wordsDict.
• Two strings word1 and word2 that are guaranteed to be present in wordsDict.

• There is exactly one valid solution.
• You may not reuse the same element for both words.
• word1 and word2 can be the same or different.

Thought Process

To solve this problem, we first consider a brute-force approach: for every occurrence of word1, check the distance to every occurrence of word2 and keep track of the minimum.

However, this is inefficient for large lists because it requires nested loops, making the time complexity high.

To optimize, we can use a single pass through the list, keeping track of the most recent indices where word1 and word2 appear. Every time we see one of the target words, we check the distance to the last seen occurrence of the other word, updating our minimum if needed.

This approach is both intuitive and efficient, as it leverages the fact that we only need to remember the last position of each word to calculate current distances.

Solution Approach

The optimized algorithm works as follows:

1. Initialize two variables, index1 and index2, to keep track of the most recent positions of word1 and word2 as we scan through wordsDict.
2. Initialize a variable min_distance with a large value (such as the length of the list).
3. Iterate through wordsDict with an index i:
• If wordsDict[i] is word1, update index1 to i.
• If wordsDict[i] is word2, update index2 to i.
• After each update, if both indices are valid (not -1), compute abs(index1 - index2) and update min_distance if this value is smaller.
4. After finishing the loop, min_distance will hold the shortest distance between the two words.

Example Walkthrough

Let's use the input wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice".

Step-by-step:

• Initialize index1 = -1, index2 = -1, min_distance = 5 (length of list).
• i = 0: "practice" matches word2, so index2 = 0.
• i = 1: "makes" (no match).
• i = 2: "perfect" (no match).
• i = 3: "coding" matches word1, so index1 = 3.
• Now both indices are valid: abs(3 - 0) = 3. Update min_distance = 3.
• i = 4: "makes" (no match).

Time and Space Complexity

Brute-Force Approach:

• For every occurrence of word1, scan the list for every occurrence of word2.
• This results in O(N^2) time complexity, where N is the length of wordsDict.
• Space complexity is O(1) (no extra space except variables).

• We scan the list once, updating indices and minimum distance on the fly.
• Time complexity is O(N), since we only traverse the list once.
• Space complexity remains O(1), as we use only a few variables.

Summary

To solve the Shortest Word Distance problem efficiently, we use a single-pass algorithm that tracks the latest positions of each target word. This approach avoids unnecessary nested loops, resulting in a simple, elegant, and highly efficient solution. By focusing on just the last seen occurrences, we ensure the minimum distance is always up-to-date, and the code remains easy to understand and maintain.

Code Implementation

class Solution:
    def shortestDistance(self, wordsDict, word1, word2):
        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, abs(index1 - index2))
            elif word == word2:
                index2 = i
                if index1 != -1:
                    min_distance = min(min_distance, abs(index1 - index2))
        return min_distance
      

class Solution {
public:
    int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
        int index1 = -1, index2 = -1;
        int min_distance = wordsDict.size();
        for (int i = 0; i < wordsDict.size(); ++i) {
            if (wordsDict[i] == word1) {
                index1 = i;
                if (index2 != -1)
                    min_distance = min(min_distance, abs(index1 - index2));
            } else if (wordsDict[i] == word2) {
                index2 = i;
                if (index1 != -1)
                    min_distance = min(min_distance, abs(index1 - index2));
            }
        }
        return min_distance;
    }
};
      

class Solution {
    public int shortestDistance(String[] wordsDict, String word1, String word2) {
        int index1 = -1, index2 = -1;
        int minDistance = wordsDict.length;
        for (int i = 0; i < wordsDict.length; i++) {
            if (wordsDict[i].equals(word1)) {
                index1 = i;
                if (index2 != -1) {
                    minDistance = Math.min(minDistance, Math.abs(index1 - index2));
                }
            } else if (wordsDict[i].equals(word2)) {
                index2 = i;
                if (index1 != -1) {
                    minDistance = Math.min(minDistance, Math.abs(index1 - index2));
                }
            }
        }
        return minDistance;
    }
}
      

var shortestDistance = function(wordsDict, word1, word2) {
    let index1 = -1, index2 = -1;
    let minDistance = wordsDict.length;
    for (let i = 0; i < wordsDict.length; i++) {
        if (wordsDict[i] === word1) {
            index1 = i;
            if (index2 !== -1) {
                minDistance = Math.min(minDistance, Math.abs(index1 - index2));
            }
        } else if (wordsDict[i] === word2) {
            index2 = i;
            if (index1 !== -1) {
                minDistance = Math.min(minDistance, Math.abs(index1 - index2));
            }
        }
    }
    return minDistance;
};