Code Implementation

from collections import defaultdict

class WordDistance:
    def __init__(self, wordsDict):
        self.word_indices = defaultdict(list)
        for i, word in enumerate(wordsDict):
            self.word_indices[word].append(i)

    def shortest(self, word1, word2):
        indices1 = self.word_indices[word1]
        indices2 = self.word_indices[word2]
        i, j = 0, 0
        min_dist = float('inf')
        while i < len(indices1) and j < len(indices2):
            min_dist = min(min_dist, abs(indices1[i] - indices2[j]))
            if indices1[i] < indices2[j]:
                i += 1
            else:
                j += 1
        return min_dist
      

class WordDistance {
public:
    unordered_map<string, vector<int>> word_indices;

    WordDistance(vector<string>& wordsDict) {
        for (int i = 0; i < wordsDict.size(); ++i) {
            word_indices[wordsDict[i]].push_back(i);
        }
    }

    int shortest(string word1, string word2) {
        const vector<int>& indices1 = word_indices[word1];
        const vector<int>& indices2 = word_indices[word2];
        int i = 0, j = 0, min_dist = INT_MAX;
        while (i < indices1.size() && j < indices2.size()) {
            min_dist = min(min_dist, abs(indices1[i] - indices2[j]));
            if (indices1[i] < indices2[j]) ++i;
            else ++j;
        }
        return min_dist;
    }
};
      

class WordDistance {
    Map<String, List<Integer>> wordIndices;

    public WordDistance(String[] wordsDict) {
        wordIndices = new HashMap<>();
        for (int i = 0; i < wordsDict.length; i++) {
            wordIndices.computeIfAbsent(wordsDict[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> indices1 = wordIndices.get(word1);
        List<Integer> indices2 = wordIndices.get(word2);
        int i = 0, j = 0, minDist = Integer.MAX_VALUE;
        while (i < indices1.size() && j < indices2.size()) {
            minDist = Math.min(minDist, Math.abs(indices1.get(i) - indices2.get(j)));
            if (indices1.get(i) < indices2.get(j)) i++;
            else j++;
        }
        return minDist;
    }
}
      

class WordDistance {
    constructor(wordsDict) {
        this.wordIndices = {};
        for (let i = 0; i < wordsDict.length; i++) {
            if (!(wordsDict[i] in this.wordIndices)) {
                this.wordIndices[wordsDict[i]] = [];
            }
            this.wordIndices[wordsDict[i]].push(i);
        }
    }

    shortest(word1, word2) {
        const indices1 = this.wordIndices[word1];
        const indices2 = this.wordIndices[word2];
        let i = 0, j = 0, minDist = Infinity;
        while (i < indices1.length && j < indices2.length) {
            minDist = Math.min(minDist, Math.abs(indices1[i] - indices2[j]));
            if (indices1[i] < indices2[j]) i++;
            else j++;
        }
        return minDist;
    }
}
      

Problem Description

You are given a list of words called wordsDict. You need to design a class WordDistance that supports two operations:

• Initialization: The class is initialized with the wordsDict array.
• Query: Given two words word1 and word2, return the shortest distance between any occurrence of word1 and word2 in the list. The distance is the absolute difference of their indices.

• There is exactly one valid answer for each query.
• The same word can appear multiple times, but you may not use the same index twice for a query.
• The shortest method may be called multiple times, so your solution should be efficient for repeated queries.

Thought Process

At first glance, the problem seems similar to finding the minimum distance between two elements in an array. The brute-force approach would be, for each query, to scan the entire list and compare every occurrence of word1 with every occurrence of word2, keeping track of the minimum distance.

However, since the shortest method may be called many times, this would be inefficient. We need a way to process queries quickly. This suggests preprocessing the list to store the positions of each word, so that looking up all positions of a word is fast. Then, the problem reduces to finding the minimum difference between two sorted lists of indices, which can be solved efficiently using a two-pointer technique.

Solution Approach

To efficiently support repeated queries, we use the following steps:

1. Preprocessing (Initialization):
   • Go through wordsDict once.
   • For each word, store all its indices in a hash map (dictionary), where the key is the word and the value is a list of indices at which the word occurs.
2. Processing a Query:
   • Given two words, retrieve their lists of indices from the hash map.
   • Both lists are already sorted (since we added indices in order).
   • Use a two-pointer technique:
     • Start with pointers at the beginning of both lists.
     • At each step, compute the absolute difference between the pointed indices.
     • Move the pointer that points to the smaller index forward, since increasing the smaller index may reduce the difference.
     • Repeat until one list is exhausted.
     • Keep track of the minimum difference found.

This approach ensures fast initialization and very fast queries, even if there are many.

Example Walkthrough

Let's consider wordsDict = ["practice", "makes", "perfect", "coding", "makes"] and a query for word1 = "coding", word2 = "practice".

• After preprocessing, the hash map will look like:
  • "practice": [0]
  • "makes": [1, 4]
  • "perfect": [2]
  • "coding": [3]
• For the query, we get:
  • Indices of "coding": [3]
  • Indices of "practice": [0]
• Using two pointers:
  • Start with i=0 (3) and j=0 (0). The difference is |3-0| = 3.
  • Since there is only one index in each list, we're done. The answer is 3.
• For another query, word1 = "makes", word2 = "coding":
  • Indices of "makes": [1, 4]
  • Indices of "coding": [3]
  • i=0 (1), j=0 (3): |1-3|=2. Move i to 1 (4).
  • i=1 (4), j=0 (3): |4-3|=1. Move j to 1 (out of bounds).
  • Minimum found is 1.

Time and Space Complexity

Brute-force Approach:

• For each query, scan the entire wordsDict to find all occurrences of both words and compare every pair.
• Time per query: O(N^2) in the worst case (if both words appear many times).
• Space: O(1) extra (if not storing indices).

• Preprocessing: O(N), where N is the length of wordsDict, to build the hash map.
• Query time: O(M + K), where M and K are the counts of word1 and word2 in the list (since we step through both lists once).
• Space: O(N), for storing all indices of all words.

The optimized approach is much faster for repeated queries.

Summary

By preprocessing the word list to store all indices for each word, we can answer multiple shortest-distance queries efficiently. The two-pointer technique leverages the naturally sorted order of indices, making each query much faster than a brute-force search. This design is elegant because it separates preprocessing from querying, and each part is optimal for its role.