Shortest Word Distance III

Updated on 03 July, 2025
Shortest Word Distance III header image

Problem Statement

The task requires finding the shortest distance between two specified words in a given list of words, wordsDict. The words for comparison, word1 and word2, are guaranteed to be present in the list. The "shortest distance" refers to the minimum number of indices that separate the two words in the array. It is important to consider that word1 and word2 might refer to the same word, adding a layer of complexity since one has to find the minimum distance between two occurrences of the same word if they are identical. The problem focuses on efficiently identifying and calculating this minimum distance while navigating through the nuances of potential word repetition and different words.

Examples

Example 1

Input:

wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"

Output:

1

Example 2

Input:

wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"

Output:

3

Constraints

  • 1 <= wordsDict.length <= 105
  • 1 <= wordsDict[i].length <= 10
  • wordsDict[i] consists of lowercase English letters.
  • word1 and word2 are in wordsDict.

Approach and Intuition

This task can be tackled efficiently by iterating through the list wordsDict and using a few variables to keep track of the positions of the words and the shortest distance found.

  1. Initialize two variables, index1 and index2, to record the last seen indices of word1 and word2 respectively. Both are initialized to some dummy values indicating they haven't been encountered yet.
  2. Create a variable min_distance initialized to a large number that will store the shortest distance found during the iteration.
  3. As you iterate through wordsDict, check for the occurrences of word1 and word2.
  4. If word1 is encountered, update index1. If word2 is also encountered (either as a separate word or the same as word1), update index2.
  5. After updating indices, if both index1 and index2 are valid (i.e., they have been updated at least once from their initial dummy values), compute the distance between the two indices.
  6. If the computed distance is smaller than min_distance, update min_distance.
  7. Continue this process until the end of the list. The value in min_distance at the end of the iteration will be the shortest distance between word1 and word2.

This method efficiently computes the shortest distance with just one pass through the list, making it optimal considering the constraints provided.

Solutions

  • C++
cpp
class Solution {
public:
    int findMinDistance(vector<string>& dictionary, string w1, string w2) {
        int minDist = INT_MAX;
        int lastIndex = -1;
        for (int idx = 0; idx < dictionary.size(); idx++) {
            if (dictionary[idx] == w1 || dictionary[idx] == w2) {
                if (lastIndex != -1 && (dictionary[lastIndex] != dictionary[idx] || w1 == w2)) {
                    minDist = min(minDist, idx - lastIndex);
                }
                lastIndex = idx;
            }
        }  
        return minDist;
    }
};

This C++ solution aims to address the problem of finding the shortest distance between two words in an array, which may be the same word (hence considering occurrences of a single word). The implementation is straightforward, focusing on minimizing iterations and effectively utilizing storage to track indices.

  • The function findMinDistance receives a vector<string> dictionary containing the words, and two string variables, w1 and w2, representing the words for which the distance needs to be calculated.
  • An integer minDist is initialized to INT_MAX to keep track of the minimum distance found during the iteration.
  • Another integer lastIndex is initialized to -1 and serves as a marker to store the index of the previous occurrence of either w1 or w2.
  • The function then iterates over the dictionary with a for loop. For each word at the current index (idx):
    • If the current word matches w1 or w2, the algorithm checks if a previous index (lastIndex) was recorded and whether the word at lastIndex is different from the current one, or it is the same (in scenarios where w1 equals w2).
    • If the conditions hold true, it updates minDist to the minimum value between the stored minDist and the difference between idx and lastIndex.
    • lastIndex is then set to the current idx.
  • Finally, the function returns minDist, representing the shortest distance between the occurrences of w1 and w2.

This approach ensures that the solution is efficient with a time complexity of O(n), where n is the length of the dictionary, as it processes each word sequentially and performs minimal operations per word. The space complexity is O(1) since it only uses a few additional variables regardless of the input size.

  • Java
java
class Solution {
    public int findMinDistance(String[] wordsArray, String firstWord, String secondWord) {
        int minDistance = Integer.MAX_VALUE;
        int lastIndex = -1;
    
        for (int index = 0; index < wordsArray.length; index++) {
            if (wordsArray[index].equals(firstWord) || wordsArray[index].equals(secondWord)) {
                if (lastIndex != -1 && (!wordsArray[lastIndex].equals(wordsArray[index]) || firstWord.equals(secondWord))) {
                    minDistance = Math.min(minDistance, index - lastIndex);
                }
                lastIndex = index;
            }
        }
        return minDistance;
    }
}

The Java solution provided aims to find the minimum distance between two given words in an array of words, where the same word can also be queried for its closest repeat. The function findMinDistance accepts an array of strings (wordsArray), and two strings (firstWord and secondWord) representing the words for which the distance is to be calculated.

Here’s a breakdown of how the logic is implemented:

  • Initialize minDistance with Integer.MAX_VALUE to track the smallest distance found.
  • Use lastIndex initialized to -1 to store the index of the last found target word.
  • Iterate through the wordsArray using index.
  • Check if the current word is either firstWord or secondWord.
  • If lastIndex is not -1 and either the last word is not the same as the current word (i.e., searching for the distance between different words) or when both target words are the same (i.e., finding the shortest distance between repeats of the same word), update minDistance with the smaller value between the previously recorded minDistance and the difference between index and lastIndex.
  • Update lastIndex to the current index.
  • After looping through the array, return minDistance.

This simple yet effective approach handles cases where both target words are the same or different, efficiently determining the shortest distance in a single pass through the array, making it optimal for scenarios where the word list is large or dynamic.

Comments

No comments yet.