Find the minimum distance between the given two words
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 3Input: S = {“Beginner”, “for”, “Beginner”, “contribute”, “practice”}, word1 = “Beginner”, word2 = “practice”
Output: 2
Explanation: Minimum distance between the words “Beginner” 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++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to return shortest distance int shortestDistance(vector<string>& s, string word1, string word2) { int d1 = -1, d2 = -1; int ans = INT_MAX; // Traverse the string 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 the answer return ans; } // Driver Code int main() { vector<string> S = { "the" , "quick" , "brown" , "fox" , "quick" }; string word1 = "the" , word2 = "fox" ; // Function Call cout << shortestDistance(S, word1, word2); return 0; } |
C
#include <limits.h> #include <stdio.h> #include <string.h> // Function to return shortest distance int shortestDistance( char s[][10], int n, char * word1, char * word2) { int d1 = -1, d2 = -1; int ans = INT_MAX; // Traverse the string for ( int i = 0; i < n; i++) { if ( strcmp (s[i], word1) == 0) d1 = i; if ( strcmp (s[i], word2) == 0) d2 = i; if (d1 != -1 && d2 != -1) ans = ans < abs (d1 - d2) ? ans : abs (d1 - d2); } // Return the answer return ans; } // Driver Code int main() { char S[][10] = { "the" , "quick" , "brown" , "fox" , "quick" }; int n = 5; char * word1 = "the" ; char * word2 = "fox" ; // Function Call printf ( "%d" , shortestDistance(S, n, word1, word2)); return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to return shortest distance static int shortestDistance(String[] s, String word1, String word2) { int d1 = - 1 , d2 = - 1 ; int ans = Integer.MAX_VALUE; // Traverse the string for ( int i = 0 ; i < s.length; i++) { if (s[i] == word1) d1 = i; if (s[i] == word2) d2 = i; if (d1 != - 1 && d2 != - 1 ) ans = Math.min(ans, Math.abs(d1 - d2)); } // Return the answer return ans; } // Driver Code public static void main (String[] args) { String[] S = { "the" , "quick" , "brown" , "fox" , "quick" }; String word1 = "the" , word2 = "fox" ; // Function Call System.out.println(shortestDistance(S, word1, word2)); } } // This code is contributed by Pushpesh Raj. |
Python3
# Python3 code to implement the approach # Function to return shortest distance def shortestDistance(s, word1, word2) : d1 = - 1 ; d2 = - 1 ; ans = 100000000 ; # Traverse the string for i in range ( len (s)) : if (s[i] = = word1) : d1 = i; if (s[i] = = word2) : d2 = i; if (d1 ! = - 1 and d2 ! = - 1 ) : ans = min (ans, abs (d1 - d2)); # Return the answer return ans; # Driver Code if __name__ = = "__main__" : S = [ "the" , "quick" , "brown" , "fox" , "quick" ]; word1 = "the" ; word2 = "fox" ; # Function Call print (shortestDistance(S, word1, word2)); # This code is contributed by AnkThon |
C#
// C# code to implement the approach using System; public class GFG { // Function to return shortest distance static int shortestDistance( string [] s, string word1, string word2) { int d1 = -1, d2 = -1; int ans = Int32.MaxValue; // Traverse the string for ( int i = 0; i < s.Length; i++) { if (s[i] == word1) d1 = i; if (s[i] == word2) d2 = i; if (d1 != -1 && d2 != -1) ans = Math.Min(ans, Math.Abs(d1 - d2)); } // Return the answer return ans; } // Driver Code static public void Main() { String[] S = { "the" , "quick" , "brown" , "fox" , "quick" }; String word1 = "the" , word2 = "fox" ; // Function Call Console.WriteLine( shortestDistance(S, word1, word2)); } } // This code is contributed by Rohit Pradhan |
Javascript
// Javascript program for above approach // Function to return shortest distance function shortestDistance(s, word1, word2) { let d1 = -1, d2 = -1; let ans = Number.MAX_VALUE; // Traverse the string for (let i = 0; i < s.length; i++) { if (s[i] == word1) d1 = i; if (s[i] == word2) d2 = i; if (d1 != -1 && d2 != -1) ans = Math.min(ans, Math.abs(d1 - d2)); } // Return the answer return ans; } // Driver Code let S = [ "the" , "quick" , "brown" , "fox" , "quick" ]; let word1 = "the" , word2 = "fox" ; // Function Call console.log(shortestDistance(S, word1, word2)); // This code is contributed by sanjoy_62. |
PHP
<?php // Function to return shortest distance function shortestDistance( $s , $word1 , $word2 ) { $d1 = -1; $d2 = -1; $ans = PHP_INT_MAX; // Traverse the string for ( $i = 0; $i < count ( $s ); $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 the answer return $ans ; } // Driver Code $S = array ( "the" , "quick" , "brown" , "fox" , "quick" ); $word1 = "the" ; $word2 = "fox" ; // Function Call echo shortestDistance( $S , $word1 , $word2 ); // This code is contributed by Kanishka Gupta ?> |
Output
3
Time Complexity: O(N*L), where N is number of strings and L is size of maximum string.
Auxiliary Space: O(1)
Contact Us