⚡Flashcard Drill➔
NeetCode #158LC-244MediumArrays & Hashing
← Back to All Problems

#158 · #244 · Shortest Word Distance II(最短单词距离 II)

📌 Problem Statement & Constraints

Design a class that is initialised with an array of strings wordsDict and answers repeated queries shortest(word1, word2) returning the shortest distance between the two words. Constraints: 1 <= wordsDict.length <= 3 * 10^4; up to 10^4 queries.

💡 Core Algorithmic Approaches

  1. Precompute a map from word to the sorted list of its indices. Preprocessing is O(n).
  2. Each query is then a merge of two sorted index lists, which is O(k1 + k2).
  3. Advance the pointer whose index is smaller, since the other list's next element can only be closer.
  4. This is the standard two-pointer merge on sorted lists and avoids re-scanning the whole array per query.

💻 Benchmark Python3 Implementation

class WordDistance:
    def __init__(self, wordsDict: List[str]):
        from collections import defaultdict
        self.pos = defaultdict(list)
        for i, w in enumerate(wordsDict):
            self.pos[w].append(i)          # sorted by construction

    def shortest(self, word1: str, word2: str) -> int:
        a, b = self.pos[word1], self.pos[word2]
        i = j = 0
        best = float("inf")
        while i < len(a) and j < len(b):
            best = min(best, abs(a[i] - b[j]))
            if a[i] < b[j]:                # advance the smaller index
                i += 1
            else:
                j += 1
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) preprocessing, then O(k1 + k2) per query where k1, k2 are the occurrence counts of the two words.
💾 Space Complexity
O(n) for the index lists.

⚠️ Interview Pitfalls & Follow-ups

  • Re-scanning the array per query: O(n) per query, i.e. O(n * q) overall, which is far too slow for 10^4 queries.
  • Advancing both pointers: the merge would skip candidate pairs; advance only the smaller index.
  • Sorting the index lists at query time: they are built in increasing order, so no sort is needed.
  • Assuming the two words differ: the class supports the same word twice, in which case the answer is the minimum gap between consecutive occurrences.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems