Shortest Word Distance II
The 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
Hiring now
Linkedin has 196 open roles right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Software Engineer - Systems and Infrastructure
Mountain View, CA, United States
Staff Software Engineer
Mountain View, CA, United States
Staff Software Engineer, Systems Infrastructure
Bengaluru, KA, India
Next question