Convert string1 to string2 in one edit


StringViews 1687

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.

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.

   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

 

Translate »