Convert string1 to string2 in one edit  


String

Edits  

1.    Add a character.
2.    Delete a character.
3.    Change a character.  

find if we can convert a string string1 to string2 by using exactly one edit.  

Examples

a) Input strings :
string1 : code
string2 : cope
Output : Yes
Here, we can convert d to p to convert string1 to string2.

b) Input strings :
string1 : code
string2 : codes
Output : Yes
Here, we can delete s to convert string1 to string2.

c) Input strings :
string1 : code
string2 : cod
Output : Yes
Here, we can add e to convert string1 to string2.

d) Input strings :
string1 : code
string2 : cosec
Output : No
Here, we can convert d to s and add c to convert string1 to string2. It takes two edits, Therefore No.

Please click Like if you loved this article?

Time complexity : O(n)

Algorithm  

Traverse both strings and keep track of count of different characters, Let the strings be string1 and string2,

1. Length of string1 is m and string2 is n.

2. If difference between m and n is greater than 1, return false.

3. Initialize edit_count = 0

4. Travers both strings starting with first character,

a. If current characters don’t match, then
i. Increment edit_count
ii. If edit_count is greater than 1, return false.
iii. If length of string is more than other, only edit is to remove a character, move ahead in large string
iv. If length is same, then only possible edit is to change a character. Therefore move in both strings.

Please click Like if you loved this article?

See also
Regular Expression Matching

   b. Else, move ahead in both strings.

C++ Program  

#include <bits/stdc++.h>

using namespace std;
 
//Function return true, if edits to convert string1 to string2 is 1
//Else False
bool EditsToConvertLessThan1(string string1, string string2)
{
    int m = string1.length(), n = string2.length();//m,n lengths of strings
    if (abs(m - n) > 1)//If difference between lengths is greater than 1
    {
        return false;
    }
    int edit_count = 0;//Initialize edit_count to 0
    int i = 0, j = 0;
    while (i < m && j < n)//Traverse in both strings starting from first character
    {
        // If current characters(i,j) don't match
        if (string1[i] != string2[j])
        {
            if (edit_count == 1)
            {
                return false;
            }
            if(m > n)//If string1 is longer than string2
            {
                i++;//move in string1
            }
            else if(m < n)//If string2 is longer than string1
            {
                j++;//move in string2
            }
            else//If lengths of both strings is same
            {
                //move in both strings
                i++;
                j++;
            }
            edit_count++;// Increment edit_count
        }
        else//If current characters match
        {
            //move in both strings
            i++;
            j++;
        }
    }
    //If last character is extra in any string
    if (i < m || j < n)
    {
        edit_count++;
    }
    //If edits count is equal to 1 return true.
    //Else, false
    if (edit_count == 1)
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
//Main function
int main()
{
   string string1 = "codex";
   string string2 = "codes";
   if(EditsToConvertLessThan1(string1, string2))
   {
    cout<<"Yes";
   }
   else
   {
    cout<<"No";
   }
   return 0;
}

Try It

 

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh