Shortest Word Distance - C Solution

1. Introduction

This blog post addresses a fundamental problem in string and array manipulation in C programming: finding the shortest distance between two words in an array of strings. This problem is essential for understanding basic array traversal and comparison operations, frequently encountered in data analysis and text processing tasks.

Problem

Given an array of strings (words) and two different words word1 and word2, the objective is to find the shortest distance between these two words in the list. The distance is defined as the number of positions between the two words.

2. Solution Steps

1. Initialize variables to store the indices of the latest occurrences of word1 and word2.

2. Iterate through the array of strings.

3. Update the index variables when either word1 or word2 is found.

4. Calculate the distance each time both words have been found, and update the minimum distance if necessary.

3. Code Program

#include <stdio.h>
#include <string.h>
#include <limits.h>

// Function to find the shortest distance between two words in an array of strings
int shortestDistance(char **words, int wordsSize, char *word1, char *word2) {
    int index1 = -1, index2 = -1; // Initialize indices for the two words
    int minDistance = INT_MAX; // Initialize minimum distance to the maximum possible value

    for (int i = 0; i < wordsSize; i++) {
        if (strcmp(words[i], word1) == 0) { // Check if current word is word1
            index1 = i; // Update index for word1
        } else if (strcmp(words[i], word2) == 0) { // Check if current word is word2
            index2 = i; // Update index for word2
        }

        if (index1 != -1 && index2 != -1) { // If both words have been found
            int distance = abs(index1 - index2); // Calculate distance
            if (distance < minDistance) {
                minDistance = distance; // Update minimum distance
            }
        }
    }

    return minDistance; // Return the shortest distance found
}

int main() {
    char *words[] = {"practice", "makes", "perfect", "coding", "makes"};
    char *word1 = "coding";
    char *word2 = "practice";
    int wordsSize = sizeof(words) / sizeof(words[0]); // Number of words in the array

    int result = shortestDistance(words, wordsSize, word1, word2); // Call the function
    printf("Output: %d\n", result); // Print the result

    return 0;
}

Output:

3

Explanation:

The program iterates through the array of strings, keeping track of the most recent positions where word1 and word2 appear. 

Each time both words are found, it calculates the distance between their current positions. The minimum of these distances is updated and finally returned.

 In the given example with words ["practice", "makes", "perfect", "coding", "makes"] and word1 as "coding" and word2 as "practice", the shortest distance between "coding" and "practice" is 3, hence the output is 3. 

This solution is efficient as it requires only one pass through the array and handles cases where the array contains multiple occurrences of the input words.