Code Implementation

class Solution:
    def shortestWordDistance(self, wordsDict, word1, word2):
        min_dist = float('inf')
        idx1, idx2 = -1, -1
        for i, word in enumerate(wordsDict):
            if word == word1:
                idx1 = i
                if word1 == word2 and idx2 != -1:
                    min_dist = min(min_dist, idx1 - idx2)
                elif idx2 != -1:
                    min_dist = min(min_dist, abs(idx1 - idx2))
                idx2 = idx1 if word1 == word2 else idx2
            elif word == word2:
                idx2 = i
                if idx1 != -1:
                    min_dist = min(min_dist, abs(idx1 - idx2))
        return min_dist
      

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

class Solution {
    public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
        int minDist = Integer.MAX_VALUE;
        int idx1 = -1, idx2 = -1;
        for (int i = 0; i < wordsDict.length; i++) {
            if (wordsDict[i].equals(word1)) {
                if (word1.equals(word2)) {
                    if (idx1 != -1)
                        minDist = Math.min(minDist, i - idx1);
                    idx1 = i;
                } else {
                    idx1 = i;
                    if (idx2 != -1)
                        minDist = Math.min(minDist, Math.abs(idx1 - idx2));
                }
            } else if (wordsDict[i].equals(word2)) {
                idx2 = i;
                if (idx1 != -1)
                    minDist = Math.min(minDist, Math.abs(idx1 - idx2));
            }
        }
        return minDist;
    }
}
      

var shortestWordDistance = function(wordsDict, word1, word2) {
    let minDist = Number.MAX_SAFE_INTEGER;
    let idx1 = -1, idx2 = -1;
    for (let i = 0; i < wordsDict.length; i++) {
        if (wordsDict[i] === word1) {
            if (word1 === word2) {
                if (idx1 !== -1)
                    minDist = Math.min(minDist, i - idx1);
                idx1 = i;
            } else {
                idx1 = i;
                if (idx2 !== -1)
                    minDist = Math.min(minDist, Math.abs(idx1 - idx2));
            }
        } else if (wordsDict[i] === word2) {
            idx2 = i;
            if (idx1 !== -1)
                minDist = Math.min(minDist, Math.abs(idx1 - idx2));
        }
    }
    return minDist;
};
      

Problem Description

You are given an array of strings called wordsDict and two strings word1 and word2. Your task is to find the shortest distance (in terms of array indices) between any occurrence of word1 and word2 in wordsDict.

• If word1 and word2 are the same word, you must find the minimal distance between any two occurrences of that word (using different indices).
• If word1 and word2 are different, find the minimal distance between any occurrence of word1 and any occurrence of word2.
• The words can appear multiple times in wordsDict.
• You may not reuse the same element for both words when they are the same.

The output should be the minimal possible distance (difference of indices) between the two words, according to the above rules.

Thought Process

The first idea that comes to mind is a brute-force solution: for every occurrence of word1, look for every occurrence of word2 and keep track of the minimal distance between their indices. This would work, but it is inefficient, especially for large arrays, since it would require checking every possible pair, leading to a time complexity of O(n²).

To optimize, we can instead scan through the array once, keeping track of the most recent indices where word1 and word2 appeared. As we encounter each word, we check if it matches either word1 or word2, update the relevant index, and compute the distance to the last occurrence of the other word. This way, we always have the most up-to-date information and can find the minimum distance efficiently.

The tricky part comes when word1 and word2 are the same. In this case, we need to ensure we are not comparing the same instance with itself, but rather the distance between two different occurrences of the same word.

Solution Approach

• Step 1: Initialize two variables, idx1 and idx2, to keep track of the most recent indices where word1 and word2 were found. Also, initialize min_dist to a large number (like infinity).
• Step 2: Loop through the wordsDict array:
  • If the current word matches word1:
  • If word1 and word2 are the same, and idx1 is not -1, calculate the distance between i and idx1, update min_dist if smaller. Then update idx1 to i.
  • If word1 and word2 are different, update idx1 to i and, if idx2 is not -1, update min_dist with the new distance.
  • If the current word matches word2 and they are different, update idx2 to i and, if idx1 is not -1, update min_dist with the new distance.
• Step 3: After the loop, return min_dist.

This approach ensures we only traverse the array once (O(n)), and always compare the most up-to-date indices, efficiently finding the minimum distance.

Example Walkthrough

Let's consider the following example:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"

• Initialize min_dist = ∞, idx1 = -1, idx2 = -1
• i = 0, word = "practice": No match, continue
• i = 1, word = "makes": idx1 = 1
• i = 2, word = "perfect": No match, continue
• i = 3, word = "coding": idx2 = 3. Now, idx1 = 1, so distance = 2. min_dist = 2
• i = 4, word = "makes": idx1 = 4. Now, idx2 = 3, so distance = 1. min_dist = 1

At the end, the shortest distance is 1 (between "makes" at index 4 and "coding" at index 3).

If word1 and word2 are the same (e.g., both "makes"), then we compare the distances between consecutive "makes" (indices 1 and 4), which is 3.

Time and Space Complexity

• Brute-force approach: For each occurrence of word1, scan the entire array for word2. If both appear k times, that is O(k²), and in the worst case O(n²).
• Optimized approach: We scan the array once, doing constant work at each step. Thus, the time complexity is O(n).
• Space complexity: Both approaches use O(1) extra space, as we only keep track of a few indices and the minimum distance.

Summary

The key to solving Shortest Word Distance III efficiently is to recognize that we can track the most recent occurrences of each target word as we iterate through the array. By updating the minimal distance on the fly, we avoid redundant comparisons and achieve an elegant O(n) solution. Special care is needed when both words are the same, but the logic remains straightforward with careful index management. This approach is both simple and highly efficient.