Join the social network of Tech Nerds, increase skill rank, get work, manage projects...

• To Check if edit distance between two strings is one

• 0
• 0
• 0
• 0
• 0
• 0
• 0
• 0
• 426
Comment on it

Edit distance between two strings is said to be one when following changes occur:-

• Deleting a character
• A character is changed
``````// C++ program to check if given two strings are
// at distance one.
#include <bits/stdc++.h>
using namespace std;

// Returns true if edit distance between s1 and
// s2 is one, else false
bool isEditDistanceOne(string s1, string s2)
{
// Find lengths of given strings
int m = s1.length(), n = s2.length();

// If difference between lengths is more than
// 1, then strings can't be at one distance
if (abs(m - n) > 1)
return false;

int count = 0; // Count of edits

int i = 0, j = 0;
while (i < m && j < n)
{
// If current characters don't match
if (s1[i] != s2[j])
{
if (count == 1)
return false;

// If length of one string is
// more, then only possible edit
// is to remove a character
if (m > n)
i++;
else if (m< n)
j++;
else //Iflengths of both strings is same
{
i++;
j++;
}

// Increment count of edits
count++;
}

else // If current characters match
{
i++;
j++;
}
}

// If last character is extra in any string
if (i < m || j < n)
count++;

return count == 1;
}

// Driver program
int main()
{
string s1 = "Demo";
string s2 = "Demo1";
isEditDistanceOne(s1, s2)? cout << "Yes": cout << "No";
return 0;
}
``````

Output:

`Yes`

Explanation of above program:-

In main program two strings are passed to isEditDistanceOne() function, this function returns true if edit distance is one else return false. In this function first length of passed string is evaluated, if the absolute difference between their length is greater than one than edit distance cannot be one and function return false but if not a while loop runs till a variable i is less than length of string1 and a variable j is less than length of string2. Within while loop characters of two string are compared. The count variable is maintained to contain value of edit count and increased accordingly. For edit distance to be one count value should be one if not one then function return false else true. The main program checks retrn value of isEditDistanceOne() function which if true prints Yes else No.

0 Comment(s)

OR
OR
Register

OR
Fill out the form below and instructions to reset your password will be emailed to you:

• Hire
• Post Projects

Post Projects

• All at 0 Cost ....
• Post Tech Job
• Select Best Bidder
• Track the Project
• Approve Work and Pay safely
• Browse Nerds
• Work
• Find Projects Find Projects
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
• Manage
• Company Company

Manage Company

• All at 0 Cost ....
• Manage Company and Employee Profiles
• Company wide Employee Productivity Reports
• Knowledge Sharing and Collaboration Tools
• Get Sales Lead and Bid for Tech Projects
• Send Invoices and Receive Payment Safely
• Learn
• Nerd Digest Nerd Digest
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
• Tech Q & A Tech Q & A
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General