# 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.

## Comments

## Post a Comment