Welcome to Subscribe On Youtube
244. Shortest Word Distance II
Description
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 betweenword1
andword2
in 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"); // return 3 wordDistance.shortest("makes", "coding"); // return 1
Constraints:
1 <= wordsDict.length <= 3 * 10^{4}
1 <= wordsDict[i].length <= 10
wordsDict[i]
consists of lowercase English letters.word1
andword2
are inwordsDict
.word1 != word2
 At most
5000
calls will be made toshortest
.
Solutions
Constructor: __init__
 A dictionary
self.d
is initialized usingdefaultdict(list)
from thecollections
module. This allows for appending indices to lists for each word without needing to check if the key exists.  The constructor iterates over
wordsDict
, enumerating each wordw
along with its indexi
. Each word’s index is appended to its corresponding list inself.d
. This setup facilitates quick access to all positions where each word appears in the list, crucial for efficiently calculating the distance between any two words later on.
Method: shortest
 Given two words,
word1
andword2
, the method retrieves their respective index lists (a
andb
) fromself.d
.  It initializes
ans
withinf
(infinity) to ensure that any actual distance found will be smaller than this initial value.  Two pointers,
i
andj
, are initialized to iterate over the index listsa
andb
, respectively.  The method enters a loop that continues until either
i
orj
has traversed its entire list. Inside the loop: The absolute difference between the current indices
a[i]
andb[j]
is calculated and used to updateans
if it’s smaller than the current value ofans
. This step finds the minimum distance between the current pair of indices.  The pointer (
i
orj
) corresponding to the smaller index is incremented. Ifa[i]
is less than or equal tob[j]
,i
is incremented; otherwise,j
is incremented. This approach ensures that the loop efficiently finds the minimum distance by always moving the pointer that points to the smaller index, thereby reducing the difference in the next iteration.
 The absolute difference between the current indices
 Once the loop completes,
ans
holds the minimum distance found between any pair of indices froma
andb
.
Example
Consider wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
, and we want to find the shortest distance between "coding"
and "makes"
:
self.d["coding"] = [3]
, andself.d["makes"] = [1, 4]
. The shortest distance calculation checks the differences
abs(3  1) = 2
andabs(3  4) = 1
.  The minimum distance is
1
, soans = 1
.
This class provides an efficient way to find the shortest distance between two words in a list, optimizing for cases where multiple queries are made against the same list by preprocessing the list into a more accessible form.

class WordDistance { private Map<String, List<Integer>> d = new HashMap<>(); public WordDistance(String[] wordsDict) { for (int i = 0; i < wordsDict.length; ++i) { d.computeIfAbsent(wordsDict[i], k > new ArrayList<>()).add(i); } } public int shortest(String word1, String word2) { List<Integer> a = d.get(word1), b = d.get(word2); int ans = 0x3f3f3f3f; int i = 0, j = 0; while (i < a.size() && j < b.size()) { ans = Math.min(ans, Math.abs(a.get(i)  b.get(j))); if (a.get(i) <= b.get(j)) { ++i; } else { ++j; } } return ans; } } /** * Your WordDistance object will be instantiated and called as such: * WordDistance obj = new WordDistance(wordsDict); * int param_1 = obj.shortest(word1,word2); */

class WordDistance { public: WordDistance(vector<string>& wordsDict) { for (int i = 0; i < wordsDict.size(); ++i) { d[wordsDict[i]].push_back(i); } } int shortest(string word1, string word2) { auto a = d[word1], b = d[word2]; int i = 0, j = 0; int ans = INT_MAX; while (i < a.size() && j < b.size()) { ans = min(ans, abs(a[i]  b[j])); if (a[i] <= b[j]) { ++i; } else { ++j; } } return ans; } private: unordered_map<string, vector<int>> d; }; /** * Your WordDistance object will be instantiated and called as such: * WordDistance* obj = new WordDistance(wordsDict); * int param_1 = obj>shortest(word1,word2); */

class WordDistance: def __init__(self, wordsDict: List[str]): self.d = defaultdict(list) for i, w in enumerate(wordsDict): self.d[w].append(i) def shortest(self, word1: str, word2: str) > int: a, b = self.d[word1], self.d[word2] ans = inf i = j = 0 while i < len(a) and j < len(b): ans = min(ans, abs(a[i]  b[j])) if a[i] <= b[j]: i += 1 else: j += 1 return ans # Your WordDistance object will be instantiated and called as such: # obj = WordDistance(wordsDict) # param_1 = obj.shortest(word1,word2) ############ class WordDistance(object): def __init__(self, words): """ initialize your data structure here. :type words: List[str] """ self.d = {} for i in range(0, len(words)): self.d[words[i]] = self.d.get(words[i], []) + [i] def shortest(self, word1, word2): """ Adds a word into the data structure. :type word1: str :type word2: str :rtype: int """ l1 = self.d[word1] l2 = self.d[word2] i = j = 0 ans = float("inf") while i < len(l1) and j < len(l2): ans = min(ans, abs(l1[i]  l2[j])) if l1[i] > l2[j]: j += 1 else: i += 1 return ans # Your WordDistance object will be instantiated and called as such: # wordDistance = WordDistance(words) # wordDistance.shortest("word1", "word2") # wordDistance.shortest("anotherWord1", "anotherWord2")

type WordDistance struct { d map[string][]int } func Constructor(wordsDict []string) WordDistance { d := map[string][]int{} for i, w := range wordsDict { d[w] = append(d[w], i) } return WordDistance{d} } func (this *WordDistance) Shortest(word1 string, word2 string) int { a, b := this.d[word1], this.d[word2] ans := 0x3f3f3f3f i, j := 0, 0 for i < len(a) && j < len(b) { ans = min(ans, abs(a[i]b[j])) if a[i] <= b[j] { i++ } else { j++ } } return ans } func abs(x int) int { if x < 0 { return x } return x } /** * Your WordDistance object will be instantiated and called as such: * obj := Constructor(wordsDict); * param_1 := obj.Shortest(word1,word2); */