💬 Discord
Sign In
NeetCode #89LC-243EasyArrays & Hashing
← Back to All Problems

#89 · #243 · Shortest Word Distance(最短单词距离)

📌 Problem Statement & Constraints

Given an array of strings wordsDict and two different strings word1 and word2, return the shortest distance between any occurrence of word1 and any occurrence of word2. Constraints: 1 <= wordsDict.length <= 3 * 10^4, word1 != word2, both guaranteed to appear.

💡 Core Algorithmic Approaches

  1. A single pass suffices: remember the most recent index where word1 was seen and where word2 was seen.
  2. Whenever both have been seen, the gap |i - j| is a candidate answer.
  3. Keeping only the most recent index of each word is sufficient, because an older occurrence can only produce a larger distance.
  4. This avoids collecting all indices and comparing every cross pair, which would be O(k1 * k2).

💻 Benchmark Python3 Implementation

class Solution:
    def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        i = j = -1                          # most recent positions
        best = float("inf")
        for k, w in enumerate(wordsDict):
            if w == word1:
                i = k
            elif w == word2:
                j = k
            if i != -1 and j != -1:
                best = min(best, abs(i - j))
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): two indices.

⚠️ Interview Pitfalls & Follow-ups

  • Collecting all indices and taking the cross-product minimum: O(k1 * k2) and unnecessary.
  • Using elif incorrectly when the two words can be equal: the problem guarantees word1 != word2, so elif is safe here. The general variant with possibly-equal words would need two separate ifs.
  • Forgetting to check that both have been seen: abs(-1 - k) would produce a spurious large distance.