Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • To Check if edit distance between two strings is one

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 808
    Comment on it

     Edit distance between two strings is said to be one when following changes occur:-

    • Adding a character.
    • Deleting a character
    • A character is changed
    // C++ program to check if given two strings are
    // at distance one.
    #include <bits/stdc++.h>
    using namespace std;
    
    // Returns true if edit distance between s1 and
    // s2 is one, else false
    bool isEditDistanceOne(string s1, string s2)
    {
    	// Find lengths of given strings
    	int m = s1.length(), n = s2.length();
    
    	// If difference between lengths is more than
    	// 1, then strings can't be at one distance
    	if (abs(m - n) > 1)
    		return false;
    
    	int count = 0; // Count of edits
    
    	int i = 0, j = 0;
    	while (i < m && j < n)
    	{
    		// If current characters don't match
    		if (s1[i] != s2[j])
    		{
    			if (count == 1)
    				return false;
    
    			// If length of one string is
    			// more, then only possible edit
    			// is to remove a character
    			if (m > n)
    				i++;
    			else if (m< n)
    				j++;
    			else //Iflengths of both strings is same
    			{
    				i++;
    				j++;
    			}
    			
    			// Increment count of edits 
    			count++;
    		}
    
    		else // If current characters match
    		{
    			i++;
    			j++;
    		}
    	}
    
    	// If last character is extra in any string
    	if (i < m || j < n)
    		count++;
    
    	return count == 1;
    }
    
    // Driver program
    int main()
    {
    string s1 = "Demo";
    string s2 = "Demo1";
    isEditDistanceOne(s1, s2)? cout << "Yes": cout << "No";
    return 0;
    }
    

    Output:

    Yes

    Explanation of above program:-

    In main program two strings are passed to isEditDistanceOne() function, this function returns true if edit distance is one else return false. In this function first length of passed string is evaluated, if the absolute difference between their length is greater than one than edit distance cannot be one and function return false but if not a while loop runs till a variable i is less than length of string1 and a variable j is less than length of string2. Within while loop characters of two string are compared. The count variable is maintained to contain value of edit count and increased accordingly. For edit distance to be one count value should be one if not one then function return false else true. The main program checks retrn value of isEditDistanceOne() function which if true prints Yes else No.

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: