224. Shortest Word Distance II
This is the repeated-query version of Shortest Word Distance: the same word list is interrogated over and over, so build a class that pays a one-time preprocessing cost and then answers each query fast.
Implement a class WordDistance:
- The constructor receives
words, an array of strings, once. shortest(word1, word2)returns the minimum|i - j|such thatwords[i] == word1andwords[j] == word2.
Every query uses two different words that both occur in the list. Because shortest may be called thousands of times, rescanning the whole array per call is the baseline to beat — think about what you can index up front so a query only touches the occurrences of the two words involved.
Example 1:
Input: WordDistance(["practice", "makes", "perfect", "coding", "makes"]); shortest("coding", "practice"); shortest("makes", "coding")
Output: 3, then 1
Explanation: "coding" (index 3) and "practice" (index 0) are 3 apart; "makes" occurs at 1 and 4, and index 4 is only 1 away from "coding" at index 3.
Example 2:
Input: WordDistance(["red", "blue", "green", "red", "yellow"]); shortest("red", "yellow"); shortest("blue", "yellow")
Output: 1, then 3
Explanation: "red" occurs at 0 and 3; index 3 is adjacent to "yellow" at index 4. "blue" only occurs at index 1, which is 3 away from index 4.
Constraints:
- 1 ≤ words.length ≤ 3 * 10⁴
- 1 ≤ words[i].length ≤ 10
- words[i] consists of lowercase English letters
- 1 ≤ q ≤ 5000 calls to shortest
- word1 and word2 both appear in words, and word1 ≠ word2
Hints:
The constructor runs once but shortest runs q times — move as much work as possible into the constructor.
In the constructor, build a hash map from each word to the sorted list of indices where it occurs. A query then only needs those two index lists.
Given two sorted index lists, find the closest pair with two pointers: compare the fronts, record the gap, and advance the pointer sitting at the smaller index — moving the larger one could only widen the gap.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: words = ["practice", "makes", "perfect", "coding", "makes"]; shortest("coding", "practice"), shortest("makes", "coding")
Expected output: [3, 1]