Table of Contents
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;
}