Domain 2MediumCORE

Shortest Word Distance II

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).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Design

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 word1 and any occurrence of word2.

Constraints & Edge Cases:

  • Array size up to 3×1043 \times 10^4.
  • Up to 5,000 queries. This implies we cannot afford an O(N)O(N) scan per query if possible; however, given the constraints (N=30kN=30k, Queries=5k5k), a naive solution might pass but risks TLE (Time Limit Exceeded) in strict environments or Python due to overhead.
  • Words can repeat frequently. If word1 appears 29 times and word2 appears 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 O(N)O(N) per query. With 5,000 queries on a dataset of size 30,000, we are looking at roughly 1.5×1081.5 \times 10^8 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 (O(1)O(1) 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 (O(∣L1∣+∣L2∣)O(|L1| + |L2|)). Given Python’s overhead with loops, leveraging bisect_left for the query logic often yields cleaner and slightly faster code.

Approach

  1. Initialization: Iterate through wordsDict. For each word at index ii, append ii to a list associated with that word in a dictionary (defaultdict(list)). This takes O(N)O(N) time and space.
  2. 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_left to 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.
  3. Optimization: By iterating through the smaller frequency count (after swapping if necessary), we minimize operations per query (O(min⁡(F1,F2)⋅log⁡(max⁡(F1,F2)))O(\min(F1, F2) \cdot \log (\max(F1, F2)))).

Complexity Analysis

  • Time (Init): O(N)O(N) where NN is wordsDict.length. We visit each element once.
  • Space: O(N)O(N) to store the indices for every word in the hash map.
  • Time (Query): Let F1,F2F1, F2 be frequencies of words. By iterating over the smaller list and binary searching on the larger one, we achieve O(min⁡(F1,F2)⋅log⁡(max⁡(F1,F2)))O(\min(F1, F2) \cdot \log (\max(F1, F2))). In worst case where both appear frequently (≈N/2\approx N/2), this is roughly O(N)O(N) 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 word appears 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, satisfying bisect_left requirements without extra sorting cost.