1. Shortest Word Distance (LeetCode)
Model answer
The task
Given a list of words and two distinct words that occur in it, find the smallest difference between their positions.
Key idea
Scan the list once, remembering the most recent position of each target word. Whenever you see either word and have already seen the other, update the best distance.
Approach
- Initialize the latest positions and the best distance.
- Visit each word with its index.
- If it matches one target, update that target’s latest position.
- When both positions are known, update the best distance.
- Return the smallest distance found.
from typing import List
class Solution:
def shortestDistance(
self, wordsDict: List[str], word1: str, word2: str
) -> int:
index1 = -1
index2 = -1
best = len(wordsDict)
for i, word in enumerate(wordsDict):
if word == word1:
index1 = i
elif word == word2:
index2 = i
if index1 != -1 and index2 != -1:
best = min(best, abs(index1 - index2))
return best
Complexity:
- Time: O(n), where n is the number of words; each word is checked once.
- Space: O(1), using only a fixed number of variables.
Common follow-ups
- What if both target words can be the same? Track consecutive occurrences of that word and compare their indices.
- What if there are many distance queries on the same list? Precompute each word’s sorted list of positions, then search those lists for each query.
- What if the list is too large to fit in memory? Stream through it once while retaining the latest target positions and the best distance found so far.