Shortest Word Distance III

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.

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.