Check whether strings are k distance apart or not

Given two strings and an integer k, write a function to check whether the given strings are k distance apart or not. That is if any charcater is mismatched or any character is to be removed then it is known as k disance apart

Example

INPUT
s1 = "cat"
s2 = "cade"
k = 2

OUTPUT
TRUE

Algorithm

1. If the difference between length of the given strings is greater than k or not. If it is greater then return FALSE

2. Find the edit distance of two strings, if edit distance is less than or equal to k then return TRUE
    Here edit distance  is the number of edit operations(insert, remove, replace) to convert s1 to s2

C++ Program

#include<bits/stdc++.h>
using namespace std;
 
// finding minimum of three numbers
int min(int x, int y, int z)
{
    return min(min(x, y), z);
}
 
int findEditDistance(string s1, string s2, int m, int n)
{
    // table to store results of subproblems
    int res[m+1][n+1];
 
    // Fill res[][] in bottom up manner
    for (int i=0; i<=m; i++)
    {
        for (int j = 0; j<=n; j++)
        {
            //If s1 string empty, then fill with s2
            if (i == 0)
                res[i][j] = j; 
 
             //If s2 string empty, then fill with s1
            else if (j == 0)
                res[i][j] = i; // Min. operations = i
 
            // If last characters are same,recur for remaining string
            else if (s1[i-1] == s2[j-1])
                res[i][j] = res[i-1][j-1];
 
            // If last character are different, consider all
            else
                res[i][j] = 1 + min(res[i][j-1],  // Insert
                                   res[i-1][j],  // Remove
                                   res[i-1][j-1]); // Replace
        }
    }
 
    return res[m][n];
}
 
//if they are k distance apart returns true
bool areKDistant(string s1, string s2, int k)
{
    int m = s1.length();
    int n = s2.length();
 
    if (abs(m-n) > k)
        return false;
 
    return (findEditDistance(s1, s2, m, n) <= k);
}
 

int main()
{
    string s1 = "cat";
    string s2 = "cade";
    int k = 2;
 
    areKDistant(s1, s2, k)? cout << "TRUE": 
                                cout << "FALSE";
 
    return 0;
}
Try It

 


< Prev
Scroll to Top