Find 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): constructor to initialize the object with the strings array wordsDict.
- int shortest(String word1, String word2): returns the shortest distance between word1 and word2 in the array wordsDict.
Examples:
Input:
[“WordDistance”, “shortest”, “shortest”]
[[[“hello”, “geek”, “gfg”, “coding”, “geek”]], [“coding”, “hello”], [“geek”, “coding”]]
Output
[null, 3, 1]
Explanation:
- The first query calls the constructor and initializes word dictionary with words: [“hello”, “geek”, “gfg”, “coding”, “geek”], therefore returns null.
- wordDistance.shortest(“coding”, “hello”) finds the minimum distance between “coding” and “hello”, that is 3 – 0 = 3
- wordDistance.shortest(“geek”, “coding”) finds the minimum distance between “coding” and “geek”, that is 4 – 3 = 1
Input:
[“WordDistance”, “shortest”, “shortest”]
[[[“abc”, “def”, “ghi”, “abc”]], [“abc”, “ghi”], [“abc”, “def”]]
Output:
[null, 1, 1]
Explanation:
- The first query calls the constructor and initializes word dictionary with words: [“abc”, “def”, “ghi”, “abc”], therefore returns null.
- wordDistance.shortest(“abc”, “ghi”) finds the minimum distance between “abc” and “ghi”, that is 3 – 2 = 1
- wordDistance.shortest(“abc”, “def”) finds the minimum distance between “abc” and “def”, that is 1 – 0 = 1
Approach: To solve the problem, follow the below idea:
Create an unordered map which stores indices of all occurrences of a word. Then, find the min difference among indices of word1 and word2. To find the minimum difference between all occurrences of word1 and word2, we can use the Two Pointer Approach where we maintain two pointers, i and j for all indices of word1 and word2. Now calculate the difference between i and j and increment whichever is smaller.
Step-by-step algorithm:
- Initialize the WordDistance class:
- The constructor WordDistance(wordsDict) takes an array of strings (the word dictionary) as input and stores the indices of each word in the dictionary using an unordered_map where the keys are the words, and the values are vectors of indices.
- Implement the shortest function:
- This function takes two strings word1 and word2 as input.
- It initializes the minDistance variable with the maximum possible value (INT_MAX).
- It then iterates through the indices of word1 and word2 using two pointers i and j.
- For each pair of indices, it calculates the absolute difference between the indices and updates the minDistance if a smaller distance is found.
- The indices are moved forward based on the relative positions of the words.
- Finally, the function returns the minDistance.
Below is the implementation of the above algorithm:
#include <bits/stdc++.h>
using namespace std;
class WordDistance {
public:
// Store the indices of each word in the dictionary
unordered_map<string, vector<int> > map;
// Constructor to initialize the data structure with the
// given word array.
WordDistance(vector<string>& wordsDict)
{
// Store the index for each occurrence of the word
for (int i = 0; i < wordsDict.size(); ++i) {
map[wordsDict[i]].push_back(i);
}
}
// Calculates the shortest distance between two given
// words in the dictionary.
int shortest(const string& word1, const string& word2)
{
// Initialize with maximum possible distance
int minDistance = INT_MAX;
// Iterate through the indices of word1 and word2
for (int i = 0, j = 0; i < map[word1].size()
&& j < map[word2].size();) {
int index1 = map[word1][i];
int index2 = map[word2][j];
// Update the minimum distance if a smaller
// distance is found
minDistance
= min(minDistance, abs(index1 - index2));
// If index1 is smaller, move to the next
// occurence of word1
if (index1 < index2) {
++i;
}
// Otherwise move to the next
// occurence of word2
else {
++j;
}
}
return minDistance;
}
};
// Driver code to test the WordDistance class
int main()
{
vector<string> words
= { "hello", "geek", "gfg", "coding", "geek" };
WordDistance wordDistance(words);
cout << "Shortest distance between 'coding' and "
"'hello': "
<< wordDistance.shortest("coding", "hello")
<< endl;
cout
<< "Shortest distance between 'geek' and 'coding': "
<< wordDistance.shortest("geek", "coding") << endl;
return 0;
}
import java.util.*;
class WordDistance {
// Store the indices of each word in the dictionary
private Map<String, List<Integer>> map;
// Constructor to initialize the data structure with the given word array.
public WordDistance(List<String> wordsDict) {
map = new HashMap<>();
// Store the index for each occurrence of the word
for (int i = 0; i < wordsDict.size(); ++i) {
String word = wordsDict.get(i);
map.putIfAbsent(word, new ArrayList<>());
map.get(word).add(i);
}
}
// Calculates the shortest distance between two given words in the dictionary.
public int shortest(String word1, String word2) {
// Initialize with maximum possible distance
int minDistance = Integer.MAX_VALUE;
List<Integer> indices1 = map.get(word1);
List<Integer> indices2 = map.get(word2);
// Iterate through the indices of word1 and word2
int i = 0, j = 0;
while (i < indices1.size() && j < indices2.size()) {
int index1 = indices1.get(i);
int index2 = indices2.get(j);
// Update the minimum distance if a smaller distance is found
minDistance = Math.min(minDistance, Math.abs(index1 - index2));
// If index1 is smaller, move to the next occurrence of word1
if (index1 < index2) {
++i;
}
// Otherwise move to the next occurrence of word2
else {
++j;
}
}
return minDistance;
}
}
// Driver code to test the WordDistance class
public class Main {
public static void main(String[] args) {
List<String> words = Arrays.asList("hello", "geek", "gfg", "coding", "geek");
WordDistance wordDistance = new WordDistance(words);
System.out.println("Shortest distance between 'coding' and 'hello': "
+ wordDistance.shortest("coding", "hello"));
System.out.println("Shortest distance between 'geek' and 'coding': "
+ wordDistance.shortest("geek", "coding"));
}
}
// This code is contributed by Shivam
from typing import List
import sys
class WordDistance:
def __init__(self, wordsDict: List[str]):
# Store the indices of each word in the dictionary
self.map = {}
# Store the index for each occurrence of the word
for i, word in enumerate(wordsDict):
if word not in self.map:
self.map[word] = []
self.map[word].append(i)
# Calculates the shortest distance between two given
# words in the dictionary.
def shortest(self, word1: str, word2: str) -> int:
# Initialize with maximum possible distance
minDistance = sys.maxsize
# Get the indices lists of both words
indices1 = self.map[word1]
indices2 = self.map[word2]
# Initialize pointers
i, j = 0, 0
# Iterate through the indices of word1 and word2
while i < len(indices1) and j < len(indices2):
index1 = indices1[i]
index2 = indices2[j]
# Update the minimum distance if a smaller
# distance is found
minDistance = min(minDistance, abs(index1 - index2))
# If index1 is smaller, move to the next
# occurrence of word1
if index1 < index2:
i += 1
# Otherwise move to the next
# occurrence of word2
else:
j += 1
return minDistance
# Driver code to test the WordDistance class
if __name__ == "__main__":
words = ["hello", "geek", "gfg", "coding", "geek"]
wordDistance = WordDistance(words)
print("Shortest distance between 'coding' and 'hello':",
wordDistance.shortest("coding", "hello"))
print("Shortest distance between 'geek' and 'coding':",
wordDistance.shortest("geek", "coding"))
# This code is contributed by Ayush Mishra
class WordDistance {
constructor(wordsDict) {
// Store the indices of each word in the dictionary
this.map = new Map();
// Store the index for each occurrence of the word
for (let i = 0; i < wordsDict.length; ++i) {
if (!this.map.has(wordsDict[i])) {
this.map.set(wordsDict[i], []);
}
this.map.get(wordsDict[i]).push(i);
}
}
// Calculates the shortest distance between two given
// words in the dictionary.
shortest(word1, word2) {
// Initialize with maximum possible distance
let minDistance = Number.MAX_SAFE_INTEGER;
const indices1 = this.map.get(word1);
const indices2 = this.map.get(word2);
// Iterate through the indices of word1 and word2
for (let i = 0, j = 0; i < indices1.length && j < indices2.length;) {
const index1 = indices1[i];
const index2 = indices2[j];
// Update the minimum distance if a smaller distance is found
minDistance = Math.min(minDistance, Math.abs(index1 - index2));
// If index1 is smaller, move to the next occurrence of word1
if (index1 < index2) {
++i;
}
// Otherwise move to the next occurrence of word2
else {
++j;
}
}
return minDistance;
}
}
// Driver code to test the WordDistance class
const words = ["hello", "geek", "gfg", "coding", "geek"];
const wordDistance = new WordDistance(words);
console.log("Shortest distance between 'coding' and 'hello': " + wordDistance.shortest("coding", "hello"));
console.log("Shortest distance between 'geek' and 'coding': " + wordDistance.shortest("geek", "coding"));
Output
Shortest distance between 'coding' and 'hello': 3 Shortest distance between 'geek' and 'coding': 1
Time Complexity:
Initialization (WordDistance constructor): O(n)
Query (shortest method): O(n)
Auxilary Space: O(n)