245. Shortest Word Distance III
Given an array of strings wordsDict and two strings word1 and word2 that already exist in the array, return the shortest distance between the occurrences 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.word1andword2are inwordsDict.
Approach 1: Binary Search
The words word1 and word2 are present at some indices in the original list. By fixing one index (say x for word1), the shortest distance to word2 would be at the index closest to x. If we have indices for word2 arranged in ascending order, we can apply binary search to find the closest index in O(log N) time, rather than iterating over all indices.
This observation allows us to solve the problem efficiently. We will store the indices of word1 in a list indices1 and the indices of word2 in a list indices2. We then iterate over indices1, and for each index, apply binary search on indices2 to find the closest index and store the minimum distance.
Algorithm
- Iterate over the list
wordsDictand store the indices ofword1inindices1and the indices ofword2inindices2. - Initialize
shortestDistanceasINT_MAX. This will store the minimum distance possible. - Iterate over
indices1. For each index:- Find the upper bound in
indices2using binary search. The upper bound will return the first index inindices2that is greater than the current index or the next-to-last index if there is no greater index. Store this index inx. - Consider both
indices2[x]andindices2[x - 1]. Ifindices2[x]is within bounds, find the distance asindices2[x] - indexand updateshortestDistanceif necessary. - If
x > 0, find the difference between the current index andindices2[x - 1]. UpdateshortestDistanceif needed.
- Find the upper bound in
- Return
shortestDistance.
class Solution {
// Returns the index pointing to the first element in the range [0, N - 1]
// that is greater than value, or N if no such element is found
int upper_bound(List indices, int value) {
int N = indices.size();
int left = 0, right = N - 1;
int index = N;
while (left <= right) {
int mid = (left + right) / 2;
if (indices.get(mid) > value) {
index = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return index;
}
public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
List indices1 = new ArrayList<>();
List indices2 = new ArrayList<>();
// Store the indices of word1 in the list indices1 and indices of word2 in the list indices2.
for (int i = 0; i < wordsDict.length; i++) {
if (wordsDict[i].equals(word1)) {
indices1.add(i);
}
if (wordsDict[i].equals(word2)) {
indices2.add(i);
}
}
// Initialize it to maximum integer as it will store the minimum distance.
int shortestDistance = Integer.MAX_VALUE;
// Iterate over the indices of word1
for (int index : indices1) {
// Find the next greater index in the list indices2
int x = upper_bound(indices2, index);
if (x != indices2.size()) {
// If x is not pointing to the last iterator, find the difference between these two indices
shortestDistance = Math.min(shortestDistance, indices2.get(x) - index);
}
if (x != 0 && indices2.get(x - 1) != index) {
// Find difference betwee index and indices[x - 1], if x > 0 and the indices are not the same.
shortestDistance = Math.min(shortestDistance, index - indices2.get(x - 1));
}
}
return shortestDistance;
}
}
Complexity Analysis
Here, N is the number of strings in the list wordsDict.
Time complexity: O(N log N).
We iterate over the indices in the list indices1 and, for each index, apply binary search over the second list indices2. Since the size of both lists can be at most N, the total time complexity is O(N log N).
Space complexity: O(N).
We need two lists, indices1 and indices2, each of which could be as large as N in the worst case. Therefore, the total space complexity is O(N).
