Home » Interview Questions » String Interview Questions » Convert string1 to string2 in one edit

Convert string1 to string2 in one edit


()

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.

READ  Find the Closest Palindrome number

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

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions