Watch 10 video solutions for Shortest Word Distance III, a medium level problem involving Array, String. This walkthrough by hakunamatasq has 3,652 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of strings wordsDict and two strings that already exist in the array word1 and word2, return the shortest distance between the occurrence of these two words in the list.
Note that word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list.
Example 1:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1
Example 2:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes" Output: 3
Constraints:
1 <= wordsDict.length <= 1051 <= wordsDict[i].length <= 10wordsDict[i] consists of lowercase English letters.word1 and word2 are in wordsDict.Problem Overview: You are given an array of words and two target strings word1 and word2. The task is to compute the smallest index distance between occurrences of these words in the list. The twist: word1 and word2 can be the same, which changes how distances must be calculated.
Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)
Scan the array and record every index where word1 and word2 appear. Then compare every valid pair and compute the absolute index difference. If the words are different, compare indices from both sets. If the words are the same, compare consecutive occurrences to avoid zero distance from the same index. This method is straightforward but inefficient because it checks many unnecessary pairs, making it quadratic in the worst case.
Approach 2: Single Pass Case Analysis (O(n) time, O(1) space)
Traverse the array once while tracking the most recent positions of the target words. Maintain two variables such as idx1 and idx2. When you encounter word1, update idx1; when you encounter word2, update idx2. After each update, compute abs(idx1 - idx2) and update the minimum distance.
The key insight appears when word1 == word2. Instead of keeping two independent indices, treat the current occurrence as the next candidate and compute the distance from the previous occurrence of the same word. Practically, you store the previous index and update the minimum whenever the word appears again. This prevents comparing the same index with itself while still capturing the closest pair.
This approach works because the closest distance must occur between two nearby occurrences in the traversal order. By updating indices during iteration, you avoid storing extra data structures and achieve linear time.
Problems like this frequently appear in interviews that test efficient scanning and state tracking over arrays. The technique is closely related to patterns used in array traversal and string processing problems, where maintaining the last seen index enables constant-time updates.
Recommended for interviews: The single-pass case analysis solution is the expected answer. It demonstrates you can reason about edge cases like identical words while maintaining O(n) efficiency. Mentioning the brute force approach first shows baseline understanding, but implementing the linear scan with correct handling for word1 == word2 shows strong problem-solving ability.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Useful for understanding the problem or when the array size is extremely small. |
| Index List + Pair Scan | O(n + k²) | O(k) | When you want clearer separation of word positions before computing distances. |
| Single Pass Case Analysis | O(n) | O(1) | Best general solution for interviews and large inputs. |