244. Shortest Word Distance II
Model: qwen3.5:9b
Topics: Hash Table,Design
FAANG asked: 1
Acceptance rate: 54.5%
Problem Breakdown
We need to design a data structure that supports two operations: initialization and querying for shortest distance between two words. The input wordsDict can contain duplicate strings (unlike the first version of this problem).
Inputs:
- Constructor takes an array of strings (
wordsDict). - Query method takes two distinct word strings (
word1,word2) guaranteed to exist in the dictionary.
Outputs:
- An integer representing the minimum absolute index difference between any occurrence of
word1and any occurrence ofword2.
Constraints & Edge Cases:
- Array size up to .
- Up to 5,000 queries. This implies we cannot afford an scan per query if possible; however, given the constraints (, Queries=), a naive solution might pass but risks TLE (Time Limit Exceeded) in strict environments or Python due to overhead.
- Words can repeat frequently. If
word1appears 29 times andword2appears once, we must handle that efficiently. - Since indices are naturally increasing as we iterate the array during initialization, our stored lists of positions will always be sorted.
Intuition
A brute-force approach would scan the entire dictionary for every query to find all occurrences of both words and compute distances. This is per query. With 5,000 queries on a dataset of size 30,000, we are looking at roughly operations in the worst case (if every word appears frequently). In Python, this often leads to TLE.
The key insight is preprocessing. We can store all indices for each unique word during initialization using a Hash Map (word -> list of indices). This allows us to retrieve positions instantly ( lookup) and reduces the query problem to finding the minimum distance between two sorted lists of integers (the index arrays).
Since these index lists are naturally sorted, we can efficiently find the closest pair. While iterating one list against another using binary search is efficient in Python due to built-in optimizations (bisect), a Two-Pointer approach on both sorted lists also works well (). Given Python’s overhead with loops, leveraging bisect_left for the query logic often yields cleaner and slightly faster code.
Approach
- Initialization: Iterate through
wordsDict. For each word at index , append to a list associated with that word in a dictionary (defaultdict(list)). This takes time and space. - Query Handling:
- Retrieve the lists of indices for both query words from our map.
- To optimize performance, we should iterate over the shorter index list to minimize loop overhead (Python loops are expensive), while using binary search on the longer list.
- For each occurrence in the smaller list, use
bisect_leftto find its position relative to occurrences of the other word. - The closest index will be either at the insertion point or immediately before it. Calculate absolute difference and track minimum.
- Optimization: By iterating through the smaller frequency count (after swapping if necessary), we minimize operations per query ().
Complexity Analysis
- Time (Init): where is
wordsDict.length. We visit each element once. - Space: to store the indices for every word in the hash map.
- Time (Query): Let be frequencies of words. By iterating over the smaller list and binary searching on the larger one, we achieve . In worst case where both appear frequently (), this is roughly but with a much smaller constant factor than linear scan. Given the constraints and Python’s speed on built-ins, this fits well within limits for 5000 calls.
Solution
import collections
from bisect import bisect_left
class WordDistance:
def __init__(self, wordsDict):
# Map each word to a list of its indices in the dictionary
self.indices = collections.defaultdict(list)
for i, word in enumerate(wordsDict):
self.indices[word].append(i)
def shortest(self, word1: str, word2: str) -> int:
# Retrieve precomputed index lists.
# Constraints guarantee these words exist.
idx1 = self.indices[word1]
idx2 = self.indices[word2] # Fixed typo from 'self_indices' to 'self.indices'
res = float('inf')
# Optimization: Iterate over the smaller list and binary search on the larger one
if len(idx1) > len(idx2):
idx1, idx2 = idx2, idx1
for i1 in idx1:
# Find insertion point in idx2 to find nearest neighbors
pos = bisect_left(idx2, i1)
# Check the element at 'pos' (if it exists and is >= i1)
if pos < len(idx2):
res = min(res, abs(i1 - idx2[pos]))
# Check the element before 'pos' (if it exists and is <= i1)
if pos > 0:
res = min(res, abs(i1 - idx2[pos-1]))
return int(res)
Edge Cases Handled
- Duplicate Words: The map stores lists of indices for every occurrence. If
wordappears multiple times, the list grows accordingly; binary search handles all positions correctly. - Single Occurrence: Works naturally as loop runs once and bisect finds exact match or neighbors immediately.
- Word Order in Array: Since we append indices sequentially during init (
enumerate), lists are always sorted ascendingly, satisfyingbisect_leftrequirements without extra sorting cost.