We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Word Distance II

Number: 244

Difficulty: Medium

Paid? Yes

Companies: LinkedIn, Anduril, Amazon

Problem Description

Design a data structure that is initialized with an array of words (wordsDict). The data structure should support queries to find the shortest distance (in terms of indices difference) between two given words (word1 and word2) from the array. Each query involves two different words, and both words are guaranteed to exist in the array.

Key Insights

  • Preprocess the input words array and maintain a mapping from each word to a list of its indices.
  • Use the stored indices to answer queries efficiently by applying a two-pointer technique to find the minimum difference between any two indices from the two words.
  • The two-pointer method works efficiently on the sorted lists of indices.
  • Preprocessing allows each query to be answered in linear time relative to the number of occurrences of the word, significantly reducing repeated computation.

Space and Time Complexity

Time Complexity:

  • Preprocessing: O(n) where n is the length of the wordsDict.
  • Query Method: O(m + k) per query, where m and k are the number of occurrences of word1 and word2 respectively. Space Complexity: O(n) to store the indices for each word.

Solution

We initialize the data structure by iterating through the words array and storing each word’s indices in a hash map (dictionary). For each query, we retrieve the sorted list of indices for both words and use a two-pointer approach to scan both lists simultaneously. At each step, we compute the absolute difference between the current indices and update the minimum distance. The pointers are then incremented based on which current index is smaller. This method ensures we check all possible pairs in an efficient manner.

Code Solutions

class WordDistance:
    def __init__(self, wordsDict):
        # Initialize a dictionary to store list of indices for each word.
        self.word_positions = {}
        for index, word in enumerate(wordsDict):
            if word not in self.word_positions:
                self.word_positions[word] = []
            self.word_positions[word].append(index)

    def shortest(self, word1, word2):
        # Retrieve the lists of positions for both words.
        positions1 = self.word_positions[word1]
        positions2 = self.word_positions[word2]
        
        i, j = 0, 0
        min_distance = float('inf')
        
        # Use a two-pointer approach to find the minimum distance.
        while i < len(positions1) and j < len(positions2):
            pos1 = positions1[i]
            pos2 = positions2[j]
            current_distance = abs(pos1 - pos2)
            min_distance = min(min_distance, current_distance)
            
            # Increment pointer for the smaller index to try and find a closer pair.
            if pos1 < pos2:
                i += 1
            else:
                j += 1
        
        return min_distance

# Example usage:
# wordDistance = WordDistance(["practice", "makes", "perfect", "coding", "makes"])
# print(wordDistance.shortest("coding", "practice"))  # Output: 3
# print(wordDistance.shortest("makes", "coding"))     # Output: 1
← Back to All Questions