# Convert string1 to string2 in one edit

0
138

## 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;
}``````