244. Shortest Word Distance II
Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.
Implement the WordDistance class:
WordDistance(String[] wordsDict)initializes the object with the strings arraywordsDict.int shortest(String word1, String word2)returns the shortest distance betweenword1andword2in the arraywordsDict.
Example 1:
Input:
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output:
[null, 3, 1]
Explanation:
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // returns 3
wordDistance.shortest("makes", "coding"); // returns 1
Constraints:
1 <= wordsDict.length <= 30,000
1 <= wordsDict[i].length <= 10
wordsDict[i] consists of lowercase English letters.
word1 and word2 are in wordsDict.
word1 != word2
At most 5,000 calls will be made to shortest
public class WordDistance {
private Map> map;
// Constructor initializes the map with the indices of each word
public WordDistance(String[] words) {
map = new HashMap>();
// Traverse the array and store indices of each word
for(int i = 0; i < words.length; i++) {
String w = words[i];
if(map.containsKey(w)) {
map.get(w).add(i);
} else {
List list = new ArrayList();
list.add(i);
map.put(w, list);
}
}
}
// Function to find the shortest distance between word1 and word2
public int shortest(String word1, String word2) {
List list1 = map.get(word1); // Get indices of word1
List list2 = map.get(word2); // Get indices of word2
int ret = Integer.MAX_VALUE; // Initialize result with maximum value
// Two pointers to traverse both lists
for(int i = 0, j = 0; i < list1.size() && j < list2.size(); ) {
int index1 = list1.get(i); // Index of word1
int index2 = list2.get(j); // Index of word2
if(index1 < index2) {
ret = Math.min(ret, index2 - index1); // Update result if smaller distance found
i++; // Move pointer in list1
} else {
ret = Math.min(ret, index1 - index2); // Update result if smaller distance found
j++; // Move pointer in list2
}
}
return ret; // Return the shortest distance
}
}
Complexity Analysis
Here, N is the number of strings in the list wordsDict.
Time complexity: O(N) for initialization and O(M) for each query.
The initialization step involves traversing the array once to build the map. This takes O(N) time, where N is the number of strings in wordsDict.
For each query, we retrieve indices from the map (which takes O(1) time) and then find the shortest distance using a two-pointer technique. Since the maximum size of lists is proportional to N, the query operation is O(M), where M is the number of indices in the lists for word1 and word2.
Space complexity: O(N).
The space complexity is dominated by the storage of indices in the map, which is proportional to the number of strings in wordsDict. Hence, the space complexity is O(N).
