Shortest Word Distance III

medium array two pointers

Problem

Given a list of words and two words word1 and word2, return the shortest distance between them. word1 and word2 may be the same.

Inputwords = ["a","b","a"], word1 = "a", word2 = "a"

Output2

two a's at positions 0 and 2 — distance 2.

words (comma-separated)

word1

word2

def shortest_distance(words, w1, w2):
    same = w1 == w2
    p1 = p2 = -1
    best = len(words)
    for i, w in enumerate(words):
        if same and w == w1:
            if p1 != -1: best = min(best, i - p1)
            p1 = i
        else:
            if w == w1: p1 = i
            elif w == w2: p2 = i
            if p1 != -1 and p2 != -1:
                best = min(best, abs(p1 - p2))
    return best

function shortestWordDistance(words, w1, w2) {
  const same = w1 === w2;
  let p1 = -1, p2 = -1, best = words.length;
  for (let i = 0; i < words.length; i++) {
    if (same && words[i] === w1) {
      if (p1 !== -1) best = Math.min(best, i - p1);
      p1 = i;
    } else {
      if (words[i] === w1) p1 = i;
      else if (words[i] === w2) p2 = i;
      if (p1 !== -1 && p2 !== -1) best = Math.min(best, Math.abs(p1 - p2));
    }
  }
  return best;
}

class Solution {
    public int shortestWordDistance(String[] words, String w1, String w2) {
        boolean same = w1.equals(w2);
        int p1 = -1, p2 = -1, best = words.length;
        for (int i = 0; i < words.length; i++) {
            if (same && words[i].equals(w1)) {
                if (p1 != -1) best = Math.min(best, i - p1);
                p1 = i;
            } else {
                if (words[i].equals(w1)) p1 = i;
                else if (words[i].equals(w2)) p2 = i;
                if (p1 != -1 && p2 != -1) best = Math.min(best, Math.abs(p1 - p2));
            }
        }
        return best;
    }
}

int shortestWordDistance(vector& words, string w1, string w2) {
    bool same = w1 == w2;
    int p1 = -1, p2 = -1, best = (int)words.size();
    for (int i = 0; i < (int)words.size(); i++) {
        if (same && words[i] == w1) {
            if (p1 != -1) best = min(best, i - p1);
            p1 = i;
        } else {
            if (words[i] == w1) p1 = i;
            else if (words[i] == w2) p2 = i;
            if (p1 != -1 && p2 != -1) best = min(best, abs(p1 - p2));
        }
    }
    return best;
}

Explanation

This is the classic "shortest distance between two words" sweep, with one twist: word1 and word2 might be the same word. We handle both cases in a single left-to-right pass, tracking the most recent positions p1 and p2.

When the two words are different, we remember the latest index of each. Every time both have been seen, we update best with abs(p1 - p2). Because we keep only the most recent sighting of each word, the closest pairing is always captured.

When the two words are the same (the same flag), every match is both occurrences at once. So whenever we hit the word, we compare against the previous occurrence using i - p1, then update p1 = i. This measures the gap between consecutive copies, which is what we want.

Example: words = ["makes","this","makes","that","makes"], word1 = word2 = "makes". The copies sit at indices 0, 2, 4; consecutive gaps are 2 and 2, so the shortest distance is 2.

It is a single pass over the list with a handful of integer variables, so it runs in O(n) time and O(1) space.

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