243. Shortest Word Distance
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 62.1%
Problem Breakdown
The problem requires finding the shortest distance between two distinct words in an array of strings. The inputs are:
wordsDict: An array of strings where each string consists of lowercase English letters.word1andword2: Two different strings that exist inwordsDict.
The output is an integer representing the minimum number of steps between the occurrences of word1 and word2 in wordsDict. The constraints ensure that word1 and word2 are distinct and present in the array.
Intuition
A brute-force approach would involve checking every pair of indices where word1 and word2 occur, calculating the distance between them, and keeping track of the minimum distance. This approach has a time complexity of O(n^2), which is inefficient for large arrays.
The key insight is to traverse the array once while maintaining the most recent positions of word1 and word2. By updating these positions as we encounter either word, we can calculate the distance between them immediately and update the minimum distance accordingly. This reduces the time complexity to O(n).
Approach
- Initialize variables to store the most recent indices of
word1andword2, both set to -1 initially. - Initialize a variable
min_distanceto a large number (e.g., infinity) to keep track of the minimum distance found. - Iterate through the array
wordsDict:- If the current word matches
word1, update its index and calculate the distance from the most recent occurrence ofword2. Updatemin_distanceif this new distance is smaller. - If the current word matches
word2, update its index and calculate the distance from the most recent occurrence ofword1. Updatemin_distanceif this new distance is smaller.
- If the current word matches
- After iterating through the array, return
min_distance.
Complexity Analysis
- Time Complexity: O(n), where n is the length of
wordsDict. We traverse the array once. - Space Complexity: O(1). We use a constant amount of extra space for variables.
Solution
def shortestDistance(wordsDict, word1, word2):
index1 = -1
index2 = -1
min_distance = float('inf')
for i in range(len(wordsDict)):
if wordsDict[i] == word1:
index1 = i
if index2 != -1:
min_distance = min(min_distance, abs(index1 - index2))
elif wordsDict[i] == word2:
index2 = i
if index1 != -1:
min_distance = min(min_distance, abs(index1 - index2))
return min_distance
Edge Cases Handled
- The array contains only one occurrence of either
word1orword2. In this case, the distance will be calculated correctly as we update indices and distances only when both words are found. - The array is very large (up to 30,000 elements). The linear time complexity ensures that the solution remains efficient even for large inputs.