Shortest Word Distance II
LinkedinThe problem
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 array wordsDict.
- int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.
**Input: **calls= ["WordDistance", "shortest", "shortest"], params = [[["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"); // return 3
- wordDistance.shortest("makes", "coding"); // return 1
**Input: **calls = ["WordDistance", "shortest", "shortest"], params = [["practice", "makes", "perfect", "coding", "makes"]], ["coding", "perfect"], ["makes", "perfect"]] **Output: **[null,1,1] Explanation:
- WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
- wordDistance.shortest("coding", "perfect"); // return 1
- wordDistance.shortest("makes", "perfect"); // return 1
- 1 <= wordsDict.length <= 3 * 104
- 1 <= wordsDict[i].length <= 10
- wordsDict[i] consists of lowercase English letters.
- word1 and word2 are in wordsDict.
- word1 != word2
- At most 5000 calls will be made to shortest.
cpp
class WordDistance {
public:
WordDistance(vector<string>& wordsDict) {
}
int shortest(string word1, string word2) {
}
};
/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance* obj = new WordDistance(wordsDict);
* int param_1 = obj->shortest(word1,word2);
*/java
class WordDistance {
public WordDistance(String[] wordsDict) {
}
public int shortest(String word1, String word2) {
}
}
/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance obj = new WordDistance(wordsDict);
* int param_1 = obj.shortest(word1,word2);
*/python
class WordDistance(object):
def __init__(self, wordsDict):
"""
:type wordsDict: List[str]
"""
def shortest(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
# Your WordDistance object will be instantiated and called as such:
# obj = WordDistance(wordsDict)
# param_1 = obj.shortest(word1,word2)javascript
/**
* @param {string[]} wordsDict
*/
var WordDistance = function(wordsDict) {
};
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
WordDistance.prototype.shortest = function(word1, word2) {
};
/**
* Your WordDistance object will be instantiated and called as such:
* var obj = new WordDistance(wordsDict)
* var param_1 = obj.shortest(word1,word2)
*/csharp
public class WordDistance
{
public WordDistance(string[] wordsDict)
{
}
public int shortest(string word1, string word2)
{
}
}
/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance obj = new WordDistance(wordsDict);
* int param_1 = obj.shortest(word1,word2);
*/go
type WordDistance struct {
// You may add fields here, e.g., wordIndices map[string][]int
}
func Constructor(wordsDict []string) WordDistance {
// Implement your constructor logic here
return WordDistance{}
}
func (wd *WordDistance) Shortest(word1 string, word2 string) int {
// Implement your shortest method logic here
return 0
}Stuck? Show a way to structure it+
- 01Map every word to its sorted occurrence indices.
- 02Build this map once in the constructor.
- 03For a query, walk two position lists with two pointers.
- 04Update the minimum absolute difference.
- 05Advance the smaller position.
Reference answer
Then expect these follow-ups
How would you handle queries where the two words are equal?
Tests: follow-up reasoning
When would caching query answers help?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question