Find the minimum distance between the given two words

By Ann Roberts On Nov 10, 2022

Improve Article

Save Article

Like Article

Improve Article

Save Article

Given a list of words followed by two words, the task is to find the minimum distance between the given two words in the list of words.

Examples:

Input: S = { “the”, “quick”, “brown”, “fox”, “quick”}, word1 = “the”, word2 = “fox”
Output: 3
Explanation: Minimum distance between the words “the” and “fox” is 3

Input: S = {“geeks”, “for”, “geeks”, “contribute”, “practice”}, word1 = “geeks”, word2 = “practice”
Output: 2
Explanation: Minimum distance between the words “geeks” and “practice” is 2

Approach: Follow the steps to solve this problem:

Initialize the variables d1 = -1, d2 = -1 and ans = INT_MAX.
Traverse the string and check:
- If, s[i] is word1 then update d1 = i.
- If, s[i] is word2 then update d2 = i.
- If, d1 != -1 and d2 != -1, then update ans = min(ans, abs(d1-d2)).
After traversing the string, return ans.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

int shortestDistance(vector<string>& s,

string word1, string word2)

{

int d1 = -1, d2 = -1;

int ans = INT_MAX;

for (int i = 0; i < s.size(); i++) {

if (s[i] == word1)

d1 = i;

if (s[i] == word2)

d2 = i;

if (d1 != -1 && d2 != -1)

ans = min(ans, abs(d1 - d2));

}

return ans;

}

int main()

{

vector<string> S

= { "the", "quick", "brown", "fox", "quick" };

string word1 = "the", word2 = "fox";

cout << shortestDistance(S, word1, word2);

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(1)

Improve Article

Save Article

Like Article

Improve Article

Save Article

Given a list of words followed by two words, the task is to find the minimum distance between the given two words in the list of words.

Examples:

Input: S = { “the”, “quick”, “brown”, “fox”, “quick”}, word1 = “the”, word2 = “fox”
Output: 3
Explanation: Minimum distance between the words “the” and “fox” is 3

Input: S = {“geeks”, “for”, “geeks”, “contribute”, “practice”}, word1 = “geeks”, word2 = “practice”
Output: 2
Explanation: Minimum distance between the words “geeks” and “practice” is 2

Approach: Follow the steps to solve this problem:

Initialize the variables d1 = -1, d2 = -1 and ans = INT_MAX.
Traverse the string and check:
- If, s[i] is word1 then update d1 = i.
- If, s[i] is word2 then update d2 = i.
- If, d1 != -1 and d2 != -1, then update ans = min(ans, abs(d1-d2)).
After traversing the string, return ans.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

int shortestDistance(vector<string>& s,

string word1, string word2)

{

int d1 = -1, d2 = -1;

int ans = INT_MAX;

for (int i = 0; i < s.size(); i++) {

if (s[i] == word1)

d1 = i;

if (s[i] == word2)

d2 = i;

if (d1 != -1 && d2 != -1)

ans = min(ans, abs(d1 - d2));

}

return ans;

}

int main()

{

vector<string> S

= { "the", "quick", "brown", "fox", "quick" };

string word1 = "the", word2 = "fox";

cout << shortestDistance(S, word1, word2);

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(1)

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.