Shortest Word Distance

Problem Statement

In this problem, you are given an array of strings denoted as wordsDict, and two distinct strings word1 and word2 which are guaranteed to be present in wordsDict. Your task is to find the shortest distance between word1 and word2 in the given list. The distance is measured as the number of words between word1 and word2 including one of them but excluding the other.

Examples

Example 1

Input:

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

Output:

3

Example 2

Input:

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

Output:

1

Constraints

• 2 <= wordsDict.length <= 3 * 104
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.
• word1 != word2

Approach and Intuition

When approaching this problem, it's important to understand that we are looking for the minimal distance between two specific words in an array. Our goal is not just to find the words but to measure how closely they occur within the array.

Here is a step-by-step method to solve this:

1. Initialize two variables, index1 and index2, to store the latest occurrences of word1 and word2. Set them to some initial value that indicates they haven't been found yet (for example, -1).

2. Iterate through the wordsDict from the first to the last element. For each word:

   • If the word matches word1, update index1 to the current index.
   • If the word matches word2, update index2 to the current index.

3. After updating either index1 or index2, check if both index1 and index2 have been updated from their initial values (i.e., both words have been found at least once).

4. If the above condition is true, compute the distance as the absolute difference between index1 and index2. Keep track of the minimum of such distances observed during the iteration.

The above approach works effectively because:

• It runs in a single pass through wordsDict, hence it is efficient with a time complexity of O(n) where n is the number of words in wordsDict.

• By continually updating the positions of word1 and word2, and calculating the distance immediately when both have been found, we ensure that the minimum distance is accurately captured, regardless of how many times the words appear in the dictionary.

This method is direct and takes advantage of the sequential nature of lists, utilizing the indices to calculate distances between elements. It efficiently narrows down the computation to necessary cases, ignoring all positions of the array that do not pertain to word1 or word2.

Solutions

class Solution {
    public int findMinDistance(String[] wordsDict, String firstWord, String secondWord) {
        int pos1 = -1, pos2 = -1;
        int shortestDistance = wordsDict.length;
        for (int idx = 0; idx < wordsDict.length; idx++) {
            if (wordsDict[idx].equals(firstWord)) {
                pos1 = idx;
            } else if (wordsDict[idx].equals(secondWord)) {
                pos2 = idx;
            }
    
            if (pos1 != -1 && pos2 != -1) {
                shortestDistance = Math.min(shortestDistance, Math.abs(pos1 - pos2));
            }
        }
        return shortestDistance;
    }
}