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
- Precompute a map from word to the sorted list of its indices. Preprocessing is O(n).
- Each query is then a merge of two sorted index lists, which is O(k1 + k2).
- Advance the pointer whose index is smaller, since the other list's next element can only be closer.
- 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.