244. Shortest Word Distance II - Detailed Explanation

Problem Statement

You are given a list of words, and you need to design a class that can answer multiple queries for the shortest distance (i.e., the absolute difference in indices) between any two given words. The class should pre-process the list in the constructor, and then efficiently return the minimum distance between word1 and word2 each time the method is called. You can assume that the two words provided in each query are distinct and that both exist in the list.

Example 1

Input:
words = ["practice", "makes", "perfect", "coding", "makes"]
Query: shortest("coding", "practice")

Output:
3

Explanation:
The only occurrence of "coding" is at index 3, and "practice" is at index 0, so the distance is |3 - 0| = 3.

Example 2

Input:
words = ["practice", "makes", "perfect", "coding", "makes"]
Query: shortest("makes", "coding")

Output:
1

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

Constraints

• The number of words can be large, and the shortest method may be called multiple times.

• Each word is a non-empty string.

• The two query words are different and are guaranteed to exist in the list.

Hints for the Approach

1. Preprocessing with a Hash Map:
   Think about storing the indices of each word in a dictionary or hash map during the initialization. This way, you only pay the cost of scanning the list once.

2. Two-Pointer Technique:
   When a query is made, use the preprocessed lists of indices for the two words and apply a two-pointer method to efficiently calculate the minimum distance.

Approach 1: Brute Force (Without Preprocessing)

Explanation

A naive solution would scan through the list for each query to find the positions of word1 and word2, then compute the minimum distance by comparing every pair of indices. For each query, this takes O(n) time where n is the length of the word list.

Drawbacks

• When there are many queries, repeating the scan each time is inefficient.
• The brute force approach becomes impractical for large lists.

Approach 2: Optimal Preprocessing with Two-Pointer Technique

Explanation

1. Preprocessing:
   In the constructor, iterate through the list of words and create a mapping (dictionary/hash map) from each word to a list of its indices. This is done only once.

2. Query Processing Using Two Pointers:
   For a given query shortest(word1, word2):

   • Retrieve the list of indices for both words.

   • Since the indices are naturally in sorted order, use two pointers to traverse these lists.

   • At each step, compute the absolute difference between the current indices from both lists.

   • Move the pointer that points to the smaller index to try and find a closer match.

   • Continue until one of the lists is fully traversed.

Detailed Walkthrough

• Step 1: In the constructor, create a mapping such that:
  map[word] = [index1, index2, ...]
  For example, with the input ["practice", "makes", "perfect", "coding", "makes"], the map would be:

  {
    "practice": [0],
    "makes": [1, 4],
    "perfect": [2],
    "coding": [3]
  }
  

• Step 2: In the shortest(word1, word2) method:

  • Retrieve the two lists of indices.

  • Initialize two pointers, one for each list.

  • While both pointers are within the bounds of their respective lists:

    • Update the minimum distance with the absolute difference between the indices.
    • Move the pointer that points to the smaller index.

  • Return the computed minimum distance.

Complexity Analysis

• Preprocessing Time: O(n), where n is the number of words.

• Query Time: O(k1 + k2) for each query, where k1 and k2 are the number of occurrences of word1 and word2, respectively.

• Space Complexity: O(n) to store the mapping of words to indices.

Code Implementation

Python Code