Shortest Word Distance - CPP Solution

1. Introduction

In this post, we tackle the "Shortest Word Distance" problem, a common question in technical interviews and algorithm challenges. This problem focuses on finding the minimum distance between two words in an array of words, demonstrating array manipulation and efficient searching in C++.

Problem

Given an array of strings wordsDict and two different strings word1 and word2, return the shortest distance between these two words in the list.

2. Solution Steps

1. Iterate through the array while tracking the most recent indices of word1 and word2.

2. Each time we find one of the words, calculate the distance to the most recent occurrence of the other word.

3. Update the minimum distance whenever a smaller distance is found.

4. Continue until the end of the array and return the minimum distance found.

3. Code Program

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

// Function to find the shortest distance between two words in an array
int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
    int index1 = -1, index2 = -1, minDistance = INT_MAX;

    for (int i = 0; i < wordsDict.size(); i++) {
        if (wordsDict[i] == word1) {
            index1 = i;
            // Calculate distance if the other word was found previously
            if (index2 != -1) {
                minDistance = min(minDistance, abs(index1 - index2));
            }
        } else if (wordsDict[i] == word2) {
            index2 = i;
            // Calculate distance if the other word was found previously
            if (index1 != -1) {
                minDistance = min(minDistance, abs(index1 - index2));
            }
        }
    }
    return minDistance;
}

int main() {
    vector<string> wordsDict = {"practice", "makes", "perfect", "coding", "makes"};
    string word1 = "coding", word2 = "practice";
    cout << "Shortest distance: " << shortestDistance(wordsDict, word1, word2) << endl;
    return 0;
}

Output:

Shortest distance: 3

Explanation:

1. The input array ["practice", "makes", "perfect", "coding", "makes"] and words "coding" and "practice" are processed.

2. The function iterates through the array, tracking the positions of "coding" and "practice".

3. Each time one of the words is found, the distance to the most recent occurrence of the other word is calculated.

4. The minimum distance found in this case is 3, between "coding" at index 3 and "practice" at index 0.

5. The function efficiently calculates the shortest distance by updating the minimum distance whenever a smaller one is found.