Question

Given a string and two words which are present in the string, find the minimum distance between the words

Example:
"the brown quick frog quick the", "the" "quick"
Min Distance: 1

"the quick the brown quick brown the frog", "the" "brown"
Min Distance: 2

C/Java code would be helpful?

Answer 1

Here is the C program for the above.

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

int main()
{
    char str[500];
    char word1[50];
    char word2[50];
    char *ptr = NULL;
    int i = 0, found1 = 0;

    printf("Enter the desired string :\n");
    fgets(str, sizeof(str), stdin);
    str[strlen(str) - 1] = '\0'; //over ride the new line.

    printf("\nEnter the two word one by one.\n");
    scanf("%s", word1);
    scanf("%s", word2);

    ptr = strtok(str, " ");
    while (ptr) {
        if (found1 == 0) {
            if (!strcmp(ptr, word1)) {
                found1 = 1;
                i = 0;
            }
        } else if (found1) {
            if (!strcmp(ptr, word2)) {
                   break;
            }
            i++;
        }

        ptr = strtok(NULL, " ");
    }

    printf("Min Distance: %d\n", i);

    return 0;
}

Answer 2

c++, implementation

int distanceTwoWordsInString(string str, string wordA, string wordB) {
    vector<int> positionA;
    vector<int> positionB;
    string sub;
    int i, start, wordIndex, indexA, indexB, distance;

    i = 0;
    start = 0;
    wordIndex = 0;
    while (i <= str.size()) {
        if (i == str.size() || str[i] == ' ') {
            sub = str.substr(start, i - start);
            start = i + 1;
            if (sub.compare(wordA) == 0) positionA.push_back(wordIndex);
            if (sub.compare(wordB) == 0) positionB.push_back(wordIndex);
            wordIndex++;
            if (i == str.size()) break;
        }
        i++;
    }

    if (positionA.size() == 0 || positionB.size() == 0) return -1;

    indexA = 0;
    indexB = 0;
    distance = wordIndex;
    while (indexA < positionA.size() && indexB < positionB.size()) {
        if (positionA[indexA] > positionB[indexB]) {
            distance = min(distance, positionA[indexA] - positionB[indexB]);
            indexB++;
        } else if (positionA[indexA] < positionB[indexB]) {
            distance = min(distance, positionB[indexB] - positionA[indexA]);
            indexA++;
        } else {
            indexA++;
        }
    }

    return distance;
}