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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Word Distance III

Number: 245

Difficulty: Medium

Paid? Yes

Companies: Palantir Technologies, LinkedIn

Problem Description

Given an array of strings wordsDict and two strings word1 and word2 that already exist in the array, return the shortest distance (in indices) between occurrences of these two words. Note that word1 and word2 may be the same, so the solution needs to handle this special case separately.

Key Insights

  • When word1 and word2 are different, maintain two indices: one for the latest occurrence of word1 and one for word2.
  • When word1 and word2 are the same, compute the distance between consecutive occurrences.
  • Perform a single pass through wordsDict to achieve optimal time complexity.

Space and Time Complexity

Time Complexity: O(n), where n is the length of wordsDict. Space Complexity: O(1) since only constant extra space is used.

Solution

The solution uses a single pass algorithm. For different words, we update the latest positions of word1 and word2 as we traverse the array and calculate the minimum distance whenever both words have been seen. When word1 and word2 are the same, we simply track the last seen index and update the minimum distance when the current index and last seen index pose a smaller gap. This conditional handling ensures the solution works correctly for both scenarios.

Code Solutions

# Python solution for Shortest Word Distance III
def shortestWordDistance(wordsDict, word1, word2):
    min_distance = float('inf')
    # Case when word1 and word2 are the same
    if word1 == word2:
        last_index = -1
        for i, word in enumerate(wordsDict):
            if word == word1:
                if last_index != -1:
                    min_distance = min(min_distance, i - last_index)
                last_index = i
    else:
        index1, index2 = -1, -1
        for i, word in enumerate(wordsDict):
            if word == word1:
                index1 = i
                if index2 != -1:
                    min_distance = min(min_distance, abs(index1 - index2))
            elif word == word2:
                index2 = i
                if index1 != -1:
                    min_distance = min(min_distance, abs(index2 - index1))
    return min_distance

# Example usage:
wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
print(shortestWordDistance(wordsDict, "makes", "coding"))  # Expected Output: 1
← Back to All Questions