Practice/LinkedIn/Leetcode 244. Shortest Word Distance II

Leetcode 244. Shortest Word Distance II

CodingMust

Problem

Design a data structure that efficiently answers queries about the minimum distance between two words in a given list. You will receive an array of words during initialization, and then need to handle multiple queries asking for the shortest distance between any two words.

The distance between two words is defined as the absolute difference between their indices in the array. When a word appears multiple times, you should consider all occurrences and return the minimum distance among all possible pairs.

Your solution should optimize for the case where the shortest method will be called many times with different word pairs on the same word list.

Requirements

1. Implement a class WordDistance with a constructor that takes a list of words
2. Implement a method shortest(word1, word2) that returns the minimum distance between the two words
3. Optimize the solution for multiple queries on the same word list
4. Both word1 and word2 are guaranteed to exist in the list
5. word1 and word2 will be different words

Constraints

• 1 ≤ words.length ≤ 3 × 10^4
• 1 ≤ words[i].length ≤ 10
• words[i] consists of lowercase English letters
• word1 and word2 are in words
• word1 ≠ word2
• At most 5000 calls will be made to shortest

Examples

Example 1:

Input: words = ["practice", "makes", "perfect", "coding", "makes"] shortest("coding", "practice") Output: 3 Explanation: "coding" is at index 3 and "practice" is at index 0, distance = |3 - 0| = 3

Example 2:

Input: words = ["practice", "makes", "perfect", "coding", "makes"] shortest("makes", "coding") Output: 1 Explanation: "makes" appears at indices 1 and 4. "coding" is at index 3. Distance between index 1 and 3 is 2 Distance between index 4 and 3 is 1 Minimum is 1

Example 3:

Input: words = ["a", "b", "c", "d", "a", "b"] shortest("a", "b") Output: 1 Explanation: Multiple occurrences exist, but indices 4 and 5 give minimum distance of 1