Given two strings, the task is to find if they are only less than or equal to k edit distance apart. It means that strings are only k edit distance apart when there are only k mismatches.
Print Yes if there are less than or equal to k mismatches, Else No.
Also, print yes if both strings are already the same.
Examples:
Input : str1 = "neveropen"
str2 = "neveropenforgeek"
k = 1
Output : Yes
Explanation: Only one character is mismatched
or to be removed i.e. s at last
Input : str1 = "nishant"
str2 = "nisha"
k = 1
Output : No
Explanation: 2 characters need to be removed
i.e. n and t
Input : str1 = "practice"
str2 = "prac"
k = 3
Output : No
Explanation: 4 characters are mismatched or to
be removed i.e. t, i, c, e at last i.e. > k
Input : str1 = "Ping" str2 = "Paging" k = 2
Output : Yes
Explanation: 2 characters need to be removed or
mismatched i.e. a and g in paging
Algorithm:
- Check if the difference in the length of both strings is greater than k. If so, return false.
- Find the edit distance of two strings. If the edit distance is less than or equal to k, return true. Else return false.
Implementation:
C++
// A Dynamic Programming based C++ program to// find minimum number operations is less than// or equal to k or not to convert str1 to str2#include <bits/stdc++.h>using namespace std;// Utility function to find minimum of three numbersint min(int x, int y, int z){ return min(min(x, y), z);}int editDistDP(string str1, string str2, int m, int n){ // Create a table to store results of subproblems int dp[m + 1][n + 1]; // Fill d[][] in bottom up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // If first string is empty, only option is to // insert all characters of second string if (i == 0) dp[i][j] = j; // Min. operations = j // If second string is empty, only option is to // remove all characters of second string else if (j == 0) dp[i][j] = i; // Min. operations = i // If last characters are same, ignore last char // and recur for remaining string else if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; // If last character are different, consider all // possibilities and find minimum else dp[i][j] = 1 + min(dp[i][j - 1], // Insert dp[i - 1][j], // Remove dp[i - 1][j - 1]); // Replace } } return dp[m][n];}// Returns true if str1 and str2 are k edit distance apart,// else false.bool areKDistant(string str1, string str2, int k){ int m = str1.length(); int n = str2.length(); if (abs(m - n) > k) return false; return (editDistDP(str1, str2, m, n) <= k);}// Driver programint main(){ // your code goes here string str1 = "geek"; string str2 = "gks"; int k = 3; areKDistant(str1, str2, k) ? cout << "Yes" : cout << "No"; return 0;} |
Java
// A Dynamic Programming based Java program to// find minimum number operations is less than// or equal to k or not to convert str1 to str2class GFG { // Utility function to find minimum // of three numbers static int min(int x, int y, int z) { return Math.min(Math.min(x, y), z); } static int editDistDP(String str1, String str2, int m, int n) { // Create a table to store // results of subproblems int dp[][] = new int[m + 1][n + 1]; // Fill d[][] in bottom up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // If first string is empty, // only option is to insert // all characters of second string if (i == 0) dp[i][j] = j; // Min. operations = j // If second string is empty, // only option is to remove // all characters of second string else if (j == 0) dp[i][j] = i; // Min. operations = i // If last characters are same, // ignore last char and recur // for remaining string else if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1]; // If last character are different, // consider all possibilities // and find minimum else dp[i][j] = 1 + min(dp[i][j - 1], // Insert dp[i - 1][j], // Remove dp[i - 1][j - 1]); // Replace } } return dp[m][n]; } // Returns true if str1 and str2 are // k edit distance apart, else false. static boolean areKDistant(String str1, String str2, int k) { int m = str1.length(); int n = str2.length(); if (Math.abs(m - n) > k) return false; return (editDistDP(str1, str2, m, n) <= k); } // driver code public static void main(String[] args) { String str1 = "geek"; String str2 = "gks"; int k = 3; if (areKDistant(str1, str2, k)) System.out.print("Yes"); else System.out.print("No"); }}// This code is contributed by Anant Agarwal. |
Python3
# A Dynamic Programming based Python3 program to # find minimum number operations is less than # or equal to k or not to convert str1 to str2 # Utility function to find minimum # of three numbers def minn(x, y, z) : return min(min(x, y), z) def editDistDP(str1, str2, m, n) : # Create a table to store results # of subproblems dp = [[0 for i in range(n + 1)] for j in range(m + 1)] # Fill d[][] in bottom up manner for i in range(m + 1): for j in range(n + 1): # If first is empty, only option is # to insert all characters of second if (i == 0) : dp[i][j] = j # Min. operations = j # If second is empty, only option is # to remove all characters of second else if (j == 0): dp[i][j] = i # Min. operations = i # If last characters are same, # ignore last char and recur # for remaining else if (str1[i - 1] == str2[j - 1]): dp[i][j] = dp[i - 1][j - 1] # If last character are different, # consider all possibilities and # find minimum else: dp[i][j] = 1 + minn(dp[i][j - 1], # Insert dp[i - 1][j], # Remove dp[i - 1][j - 1]) # Replace return dp[m][n] # Returns true if str1 and str2 are# k edit distance apart, else false. def areKDistant(str1, str2, k): m = len(str1) n = len(str2) if (abs(m - n) > k) : return False return (editDistDP(str1, str2, m, n) <= k) # Driver Code if __name__ == '__main__': str1 = "geek" str2 = "gks" k = 3 if areKDistant(str1, str2, k): print("Yes") else: print("No")# This code is contributed # by SHUBHAMSINGH10 |
C#
// A Dynamic Programming based C# // program to find minimum number// operations is less than or equal// to k or not to convert str1 to str2using System;class GFG { // Utility function to find minimum// of three numbersstatic int min(int x, int y, int z){ return Math.Min(Math.Min(x, y), z);}static int editDistDP(string str1, string str2, int m, int n){ // Create a table to store // results of subproblems int [,]dp = new int[m + 1, n + 1]; // Fill d[][] in bottom up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // If first string is empty, // only option is to insert // all characters of second string if (i == 0) // Min. operations = j dp[i, j] = j; // If second string is empty, // only option is to remove // all characters of second string else if (j == 0) // Min. operations = i dp[i, j] = i; // If last characters are same, // ignore last char and recur // for remaining string else if (str1[i - 1] == str2[j - 1]) dp[i, j] = dp[i - 1,j - 1]; // If last character are different, // consider all possibilities // and find minimum else dp[i, j] = 1 + min(dp[i, j - 1], // Insert dp[i - 1, j], // Remove dp[i - 1, j - 1]); // Replace } } return dp[m, n];}// Returns true if str1 and str2 are// k edit distance apart, else false.static bool areKDistant(string str1, string str2, int k){ int m = str1.Length; int n = str2.Length; if (Math.Abs(m - n) > k) return false; return (editDistDP(str1, str2, m, n) <= k);}// Driver Codepublic static void Main (){ string str1 = "geek"; string str2 = "gks"; int k = 3; if(areKDistant(str1, str2, k)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by vt_m. |
PHP
<?php// A Dynamic Programming based // PHP program to find minimum// number operations is less // than or equal to k or not // to convert str1 to str2// Utility function to find// minimum of three numbersfunction minn($x, $y, $z){ return min(minn($x, $y), $z);}function editDistDP($str1, $str2, $m, $n){ // Create a table to store // results of subproblems $dp[$m + 1][$n + 1] = 0; // Fill d[][] in bottom up manner for ($i = 0; $i <= $m; $i++) { for ($j = 0; $j <= $n; $j++) { // If first string is empty, // only option is to insert // all characters of second string if ($i == 0) // Min. operations = j $dp[$i][$j] = $j; // If second string is empty, // only option is to remove all // characters of second string else if ($j == 0) // Min. operations = i $dp[$i][$j] = $i; // If last characters are same, // ignore last char and recur // for remaining string else if ($str1[$i - 1] == $str2[$j - 1]) $dp[$i][$j] = $dp[$i - 1][$j - 1]; // If last character are different, // consider all possibilities and // find minimum else // Insert $dp[$i][$j] = 1 + min($dp[$i][$j - 1], // Remove $dp[$i - 1][$j], // Replace $dp[$i - 1][$j - 1]); } } return $dp[$m][$n];}// Returns true if str1 and // str2 are k edit distance // apart, else false.function areKDistant($str1, $str2, $k){ $m = strlen($str1); $n = strlen($str2); if (abs($m - $n) > $k) return false; return (editDistDP($str1, $str2, $m, $n) <= $k);}// Driver Code$str1 = "geek";$str2 = "gks";$k = 3;if(areKDistant($str1, $str2, $k)) echo"Yes" ; elseecho "No";// This code is contributed by nitin mittal. ?> |
Javascript
<script> // A Dynamic Programming based Javascript program to // find minimum number operations is less than // or equal to k or not to convert str1 to str2 // Utility function to find minimum // of three numbers function min(x, y, z) { return Math.min(Math.min(x, y), z); } function editDistDP(str1, str2, m, n) { // Create a table to store // results of subproblems let dp = new Array(m + 1); // Fill d[][] in bottom up manner for (let i = 0; i <= m; i++) { dp[i] = new Array(n + 1); for (let j = 0; j <= n; j++) { // If first string is empty, // only option is to insert // all characters of second string if (i == 0) dp[i][j] = j; // Min. operations = j // If second string is empty, // only option is to remove // all characters of second string else if (j == 0) dp[i][j] = i; // Min. operations = i // If last characters are same, // ignore last char and recur // for remaining string else if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; // If last character are different, // consider all possibilities // and find minimum else dp[i][j] = 1 + min(dp[i][j - 1], // Insert dp[i - 1][j], // Remove dp[i - 1][j - 1]); // Replace } } return dp[m][n]; } // Returns true if str1 and str2 are // k edit distance apart, else false. function areKDistant(str1, str2, k) { let m = str1.length; let n = str2.length; if (Math.abs(m - n) > k) return false; return (editDistDP(str1, str2, m, n) <= k); } let str1 = "geek"; let str2 = "gks"; let k = 3; if (areKDistant(str1, str2, k)) document.write("Yes"); else document.write("No"); </script> |
Output
Yes
Time Complexity : O(n*m), where n and m are length od string1 and string2 respectively.
Auxiliary Space : O(n*m), since we used dp[][] matrix of size n*m.
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
