244. Shortest Word Distance II

MediumDesignArrayHash TableTwo PointersString
Leetcode Link

Problem Description

The problem provides us with the task of designing a data structure that must be able to compute the shortest distance between any two distinct strings within an array of strings. This implies that we first need to initialize the data structure with an array of strings, which we'll refer to as wordsDict. Once initialized, we should be able to query this data structure with two different strings, and it should return the smallest possible index difference between these two strings within the wordsDict array.

This could be visualized as an array where we want to find the minimum distance between two elements, where the elements are the positions of the words we're interested in. For example, if wordsDict is ["practice", "makes", "perfect", "coding", "makes"], and we query for the distance between "coding" and "practice", the returned value should be 3, as the closest "practice" to "coding" is three indices away.

Intuition

To efficiently find the shortest distance between two words in the dictionary, a preprocessing step is required during initialization. We traverse the wordsDict array once and create a hash map where keys are the distinct words from the array, and values are lists of indices where each key word is located in the original array. This preprocessing step allows for a quick lookup of the positions of any word, facilitating the computation of the distances between any two words.

Once the positions are mapped, to find the shortest distance between word1 and word2, we get their list of indices from our hash map. We need to find the minimum difference between any two indices from these lists. The lists are already sorted because the indices were appended in the order they were encountered during initialization.

A two-pointer approach efficiently solves the problem of finding the minimum difference. Start with the first index of each list, and at each step, move the pointer that points to the smaller index to the next index in its list. The intuition behind this is that we try to close the gap between word1 and word2 by moving forward in the list where the current index is smaller. This approach will traverse the two lists simultaneously and will always give the smallest possible difference in indices (thus the shortest distance) between word1 and word2. The process repeats until we have fully traversed one of the lists, ensuring that no potential shorter distance is missed.

The overall time complexity for the shortest operation, after the initial preprocessing, is O(N + M), where N and M are the number of occurrences of word1 and word2 in the dictionary, respectively. The preprocessing itself is O(K), where K is the total number of words in the dictionary, with the space complexity also being O(K) for storing the hash map.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

In the reference solution, the WordDistance class is defined, which implements the required functionality. The class uses a hash map (dictionary in Python) to store the indices of each word as they appear in wordsDict. Python's defaultdict from the collections module is used to handle the automatic creation of entries for new words, with each entry being a list that gets appended with the current index (i) every time the word (w) is encountered in the array.

Here is a breakdown of the implementation:

  1. Initialization (__init__): This method takes a list of strings wordsDict as input. It iterates over wordsDict, enumerating each word with its index. For every word-index pair, it appends the index to the list that corresponds to the word in the hash map self.d. By the end of this process, we have a dictionary where each word is associated with a list of indices indicating its positions in the wordsDict array.

    1self.d = defaultdict(list)
    2for i, w in enumerate(wordsDict):
    3    self.d[w].append(i)
  2. Finding Shortest Distance (shortest): This method calculates the shortest distance between two words word1 and word2. By accessing self.d[word1] and self.d[word2], it retrieves the two lists of indices for the given words. The algorithm then initializes two pointers, i and j, starting at 0. These pointers will traverse the index lists.

    The variable ans is initialized to infinity (inf). It will be updated with the minimum difference between indices found so far as we iterate through the lists of indices.

    Following a two-pointer approach, the algorithm compares the indices at the current pointers and updates ans with the smaller of the current difference and the previously stored ans. Based on which index is smaller, the corresponding pointer (i or j) is incremented to move to the next index in the respective list.

    The loop continues until one list is fully traversed, ensuring that the minimum distance has been found:

    1a, b = self.d[word1], self.d[word2]
    2ans = inf
    3i = j = 0
    4while i < len(a) and j < len(b):
    5    ans = min(ans, abs(a[i] - b[j]))
    6    if a[i] <= b[j]:
    7        i += 1
    8    else:
    9        j += 1
    10return ans

In the above loop, at each step, because the two lists are sorted by the nature of their construction, we can guarantee that moving the pointer past the smaller index will give us a pair of indices that is potentially closer than the previous one. This algorithm effectively finds the minimum distance between the two words, which is the absolute difference between their closest indices.

The WordDistance class can then be instantiated with a string array wordsDict, and the shortest method can be called to find the shortest distance between any two words.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Let's demonstrate how the WordDistance class and its methods work using a simple example.

Suppose our wordsDict is ["the", "quick", "brown", "fox", "quick"]. We initialize the WordDistance class with this list of strings. During the initialization process, the class builds the hash map self.d which will contain:

  • "the" -> [0]
  • "quick" -> [1, 4]
  • "brown" -> [2]
  • "fox" -> [3]

Now, let's say we want to find the shortest distance between the words "brown" and "quick". We call the shortest method with these two words. Here's what happens inside this method:

  1. We access the two lists of indices for the words "brown" and "quick" from our hash map, which gives us a = [2] and b = [1, 4].

  2. We initialize two pointers i and j and a variable ans which will keep track of the minimum distance. Initially, i = 0, j = 0, ans = inf.

  3. We enter a while-loop, which will continue until we have fully traversed one of the lists.

  4. Inside the loop, we compare a[i] with b[j]. At the start, a[i] = 2 and b[j] = 1. The difference |2 - 1| = 1 is less than ans, so we update ans = 1.

  5. Since the current value at a[i] is greater than b[j], we increment j to move to the next index in list b.

  6. Now, i = 0 and j = 1, which means a[i] = 2 and b[j] = 4. The difference |2 - 4| = 2 is not less than the current ans, so ans remains 1.

  7. We've reached the end of list a, so the loop terminates.

Since we have examined all possible pairs of indices for "brown" and "quick", we have found the shortest distance to be 1, which is the minimum index difference between these words in the wordsDict.

Finally, we return ans which is 1, concluding that the shortest distance between "brown" and "quick" in the wordsDict array is 1.

Not Sure What to Study? Take the 2-min Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Python Solution

1from collections import defaultdict
2from math import inf
3
4class WordDistance:
5    def __init__(self, words_dict: List[str]):
6        # Initializing a default dictionary to store the indices of each word
7        self.indices_map = defaultdict(list)
8      
9        # Loop through the list of words and populate the indices map
10        for index, word in enumerate(words_dict):
11            self.indices_map[word].append(index)
12
13    def shortest(self, word1: str, word2: str) -> int:
14        # Retrieve the list of indices for the two words
15        indices_word1, indices_word2 = self.indices_map[word1], self.indices_map[word2]
16        # Initialize the minimum distance to infinity
17        min_distance = inf
18        # Initialize two pointers for the lists of indices
19        i, j = 0, 0
20      
21        # Iterate until we reach the end of one of the lists of indices
22        while i < len(indices_word1) and j < len(indices_word2):
23            # Update the minimum distance as the smaller between the previous
24            # minimum distance and the current distance between word1 and word2
25            min_distance = min(min_distance, abs(indices_word1[i] - indices_word2[j]))
26            # Move the pointer of the list which currently has a smaller index forward
27            if indices_word1[i] <= indices_word2[j]:
28                i += 1
29            else:
30                j += 1
31      
32        # Return the minimum distance found
33        return min_distance
34
35# Example of usage:
36# word_distance = WordDistance(["practice", "makes", "perfect", "coding", "makes"])
37# result = word_distance.shortest("coding", "practice")
38# result would have the shortest distance between "coding" and "practice" in the list
39

Java Solution

1// Class to calculate the shortest distance between two words in a dictionary.
2class WordDistance {
3    // Create a map to hold lists of indices for each word
4    private Map<String, List<Integer>> wordIndicesMap = new HashMap<>();
5
6    // Constructor takes an array of words and populates the map with the words and their indices.
7    public WordDistance(String[] wordsDict) {
8        for (int i = 0; i < wordsDict.length; ++i) {
9            // For each word, add the current index to its list in the map.
10            // If the word is not already in the map, create a new list for it.
11            wordIndicesMap.computeIfAbsent(wordsDict[i], k -> new ArrayList<>()).add(i);
12        }
13    }
14
15    // Method to find the shortest distance between two words.
16    public int shortest(String word1, String word2) {
17        // Retrieve the lists of indices for the two words.
18        List<Integer> indicesWord1 = wordIndicesMap.get(word1);
19        List<Integer> indicesWord2 = wordIndicesMap.get(word2);
20
21        // Initialize the answer with a high value to ensure it gets replaced.
22        int shortestDistance = Integer.MAX_VALUE;
23
24        // Pointers to iterate through the lists for both words.
25        int i = 0;
26        int j = 0;
27
28        // Iterate through both lists to find the smallest distance.
29        while (i < indicesWord1.size() && j < indicesWord2.size()) {
30            int indexWord1 = indicesWord1.get(i);
31            int indexWord2 = indicesWord2.get(j);
32          
33            // Update the shortest distance with the minimum distance found so far.
34            shortestDistance = Math.min(shortestDistance, Math.abs(indexWord1 - indexWord2));
35
36            // Move the pointer that points to the smaller index forward.
37            if (indexWord1 <= indexWord2) {
38                ++i;
39            } else {
40                ++j;
41            }
42        }
43        // Return the shortest distance found.
44        return shortestDistance;
45    }
46}
47
48/**
49 * The following comments are provided as an example of how you might use the WordDistance class.
50 * WordDistance object can be created by passing in a dictionary of words.
51 * You can then call the 'shortest' method to find the shortest distance between any two words.
52 */
53
54// Example of using the WordDistance class.
55/*
56WordDistance wordDistance = new WordDistance(wordsDict);
57int result = wordDistance.shortest("word1", "word2");
58*/
59

C++ Solution

1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <climits>
5using namespace std;
6
7class WordDistance {
8public:
9    // Constructor takes a reference to a vector of strings as the dictionary
10    WordDistance(vector<string>& wordsDict) {
11        // Store the indices of each word's occurrences in the dictionary
12        for (int i = 0; i < wordsDict.size(); ++i) {
13            wordIndices[wordsDict[i]].push_back(i);
14        }
15    }
16
17    // Function to find the shortest distance between two words
18    int shortest(string word1, string word2) {
19        // Retrieve the list of indices for each word
20        auto indicesWord1 = wordIndices[word1];
21        auto indicesWord2 = wordIndices[word2];
22      
23        int indexWord1 = 0; // Current index in indicesWord1
24        int indexWord2 = 0; // Current index in indicesWord2
25        int minimumDistance = INT_MAX; // Initialize minimum distance as maximum possible int value
26      
27        // Loop until we reach the end of one of the index lists
28        while (indexWord1 < indicesWord1.size() && indexWord2 < indicesWord2.size()) {
29            // Update minimumDistance with the smallest difference between indices
30            minimumDistance = min(minimumDistance, abs(indicesWord1[indexWord1] - indicesWord2[indexWord2]));
31          
32            // Move to the next index in the list, which has the smaller current index value
33            if (indicesWord1[indexWord1] < indicesWord2[indexWord2]) {
34                indexWord1++;
35            } else {
36                indexWord2++;
37            }
38        }
39        return minimumDistance; // Return the smallest distance found
40    }
41
42private:
43    // Dictionary to store words and their occurrences' indices
44    unordered_map<string, vector<int>> wordIndices;
45};
46
47// The class can be used as follows:
48// WordDistance* obj = new WordDistance(wordsDict);
49// int shortestDistance = obj->shortest(word1, word2);
50

Typescript Solution

1// Dictionary to store words and their occurrences' indices
2const wordIndices: { [word: string]: number[] } = {};
3
4// Function to initialize the word indices dictionary with a list of words
5function initializeWordDistance(wordsDict: string[]): void {
6    for (let i = 0; i < wordsDict.length; ++i) {
7        const word = wordsDict[i];
8        if (wordIndices[word] === undefined) {
9            wordIndices[word] = [];
10        }
11        wordIndices[word].push_back(i);
12    }
13}
14
15// Function to find the shortest distance between two words
16function shortest(word1: string, word2: string): number {
17    // Retrieve the list of indices for each word
18    const indicesWord1 = wordIndices[word1];
19    const indicesWord2 = wordIndices[word2];
20
21    let indexWord1 = 0; // Current index in indicesWord1
22    let indexWord2 = 0; // Current index in indicesWord2
23    let minimumDistance = Number.MAX_SAFE_INTEGER; // Initialize minimum distance as largest possible safe integer value
24
25    // Loop until we reach the end of one of the index lists
26    while (indexWord1 < indicesWord1.length && indexWord2 < indicesWord2.length) {
27        // Update minimumDistance with the smallest difference between indices
28        minimumDistance = Math.min(minimumDistance, Math.abs(indicesWord1[indexWord1] - indicesWord2[indexWord2]));
29
30        // Move to the next index in the list, which has the smaller current index value
31        if (indicesWord1[indexWord1] < indicesWord2[indexWord2]) {
32            indexWord1++;
33        } else {
34            indexWord2++;
35        }
36    }
37
38    return minimumDistance; // Return the smallest distance found
39}
40
41// Usage example:
42// initializeWordDistance(wordsDict);
43// let shortestDistance = shortest(word1, word2);
44
Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:

Time and Space Complexity

Initialization (__init__)

  • Time Complexity: O(N), where N is the length of wordsDict. This is because we're iterating through each word in the list and inserting the index into the dictionary.
  • Space Complexity: O(N), as in the worst-case scenario, we're storing the index of each word within the dictionary, which would require space proportional to the number of words.

Shortest Method (shortest)

  • Time Complexity: O(L + M), where L is the length of the list associated with word1 and M is the length of the list associated with word2. In the worst case, we traverse each list once in a single run of the while loop.
  • Space Complexity: O(1), because we're only using a few variables (i, j, ans, a, b) for calculations and not utilizing any additional space that is dependent on the size of the input.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫