3.39 Shortest Word Distance

3.39.1 Problem Metadata

3.39.2 Description

Given a lc-list of words and two target words word1 and word2, return the minimum index distance between any occurrence of word1 and word2 in the lc-list.

3.39.3 Examples

Input: words = ["practice","makes","perfect","coding","makes"], word1 = "coding", word2 = "practice"
Output: 3

3.39.4 Constraints

  • 2 <= words.length <= 10^5

3.39.5 Solution - Single Pass

3.39.5.1 Walkthrough

Scan the array while recording the latest indices of word1 and word2. Whenever both have been seen, compute their distance and track the minimum. This avoids storing full index lc-lists.

3.39.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)

3.39.5.3 Implementation Steps

  1. Initialize idx1 = idx2 = -1, answer = n.
  2. For each index i:
    • If words[i] == word1, set idx1 = i.
    • Else if words[i] == word2, set idx2 = i.
    • If both indices are valid, update answer = min(answer, |idx1 - idx2|).
  3. Return answer.

3.39.5.4 Code - Java

public int shortestDistance(String[] words, String word1, String word2) {
    int idx1 = -1;
    int idx2 = -1;
    int best = words.length;

    for (int i = 0; i < words.length; i++) {
        if (words[i].equals(word1)) {
            idx1 = i;
        } else if (words[i].equals(word2)) {
            idx2 = i;
        }

        if (idx1 != -1 && idx2 != -1) {
            best = Math.min(best, Math.abs(idx1 - idx2));
        }
    }

    return best;
}