Answer Repeated Shortest Word Distance Queries

Problem Statement

Design a class that accepts an array of strings and supports repeated queries to find the minimum distance between two distinct words in the array.

The distance between two words at indices i and j is defined as abs(i - j).

Implement the WordDistance class:

• WordDistance(words: list[str]): Initializes the object with the array of strings words.
• shortest(word1: str, word2: str) -> int: Returns the minimum distance between word1 and word2 in the original array.

Matching is case-sensitive. Both word1 and word2 are guaranteed to exist in words and will always be distinct.

Function Interface

class WordDistance:
    def __init__(self, words: list[str]):
        pass

    def shortest(self, word1: str, word2: str) -> int:
        pass

Examples

Example 1

Input:
wd = WordDistance(["practice", "makes", "perfect", "coding", "makes"])
wd.shortest("coding", "practice")
wd.shortest("makes", "coding")

Output:
3
1

Explanation:
- "coding" is at index 3 and "practice" is at index 0. The distance is abs(3 - 0) = 3.
- "makes" appears at indices 1 and 4, while "coding" is at index 3. The minimum distance is min(abs(1 - 3), abs(4 - 3)) = min(2, 1) = 1.

Constraints

• 1 <= len(words) <= 30000
• 1 <= len(words[i]) <= 10
• words[i] consists of lowercase and uppercase English letters.
• word1 and word2 are distinct and guaranteed to exist in words.
• At most 5000 calls will be made to shortest.

Edge Cases

• The minimum distance is 1 when the two words appear as immediate neighbors.
• One word may appear once while the other appears many times across the array.
• The earliest occurrences might not yield the shortest distance; all relative pairs must be evaluated.