This is a C++ Program that Solves Edit Distance Problem using Dynamic Programming technique.
There are two strings src and dest. The goal of the problem is to convert src to dest by applying minimum edit operations on string str1. The edit operations are following –
1) insert a character
2) delete a character
3) replace a character
This problem can be solved optimally using bottom up DP. We will first calculate minimum operations required to transform a prefix of the string src to a prefix of string dest. Then we will use this information to calculate minimum no. of operations required to transform a bigger prefix of src to a bigger prefix of dest.
The time complexity of this solution will be O(len1*len2).
Case-1:
str1="vish" str2="vishal" Minimum number of edit operations=2 inserting 2 chracters 'a' and 'l'
Case-2:
str1="vshkl" str2="vishal" Minimum number of edit operations=2 inserting 'i' and replacing 'k' with 'a'
Case-3:
str1="apiskal" str2="vishal" Minimum number of edit operations=3 deleting 'a', replacing 'p' with 'v' and replacing 'k' with 'h'
Here is source code of the C++ Program to Solve Edit Distance Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<iostream>
#include<string>
using namespace std;
//we will be processing the src and dest string from the rear end.
//If the current character matches in both string, we proceed for next character.
//else we will apply all the 3 operations one by one, and select the one which takes
//minimum number of overall edit operations to convert src to dest
int minEditDistanceBrute(string src, string dest, int len1, int len2)
{
//if we have already attained the dest string, we can simply remove the left out characters in src string
if(len2==0)
{
return len1;
}
//if the entire src string is process, we can simply insert all the remaining characters of dest string
if(len1==0)
{
return len2;
}
//if current character of the src and dest is same, no operation is required to be done
if(src[len1-1]==dest[len2-1])
{
return minEditDistanceBrute(src, dest, len1-1, len2-1);
}
//if current character is different for src and dest string
else
{
//if the required character of dest string is inserted in src string
int x=1+minEditDistanceBrute(src,dest,len1,len2-1);
//if the current character of src is removed
int y=1+minEditDistanceBrute(src,dest,len1-1,len2);
//if the current character of the src string is replaced with the current character of the dest string
int z=1+minEditDistanceBrute(src,dest,len1-1,len2-1);
//now, choose the operation which require minimum number of overall operations out of these
return min(x,min(y,z));
}
}
int main()
{
string src,dest;
cout<<"Enter source string ";
getline(cin, src);
cout<<"Enter destination string ";
getline(cin, dest);
int len1=src.length(); //length of src string
int len2=dest.length(); //length of dest string
cout<<"Minimum number of edit operations required for transforming \nsource string to destination string is "<<minEditDistanceBrute(src,dest,len1,len2);
cout<<endl;
return 0;
}
Here is source code of the C++ Program to Solve Edit Distance Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<iostream>
#include<string>
using namespace std;
int minEditDistance(string src, string dest, int len1, int len2)
{
int i, j;
//create a matrix of order (len1+1)*(len2+1) to memoize values
int edit[len1+1][len2+1];
//edit[i][j]=minimum number of edit operations required to transform src[0....(i-1)] to dest[0...(j-1)]
//initializing
for(i=0;i<=len1;i++)
edit[i][0]=i; //min operations required to transform src[0...i-1] to empty dest string
for(j=0;j<=len2;j++)
edit[0][j]=j; //min operations required to transform empty src to dest[0...j-1]
//now, start filling the matrix row wise
for(i=1;i<=len1;i++)
{
for(j=1;j<=len2;j++)
{
//if current character of both strings match
if(src[i-1]==dest[j-1])
{
edit[i][j]=edit[i-1][j-1];
}
//mismatch
else
{
//try applying all operations and choose the one which costs minimum
int x=1+edit[i-1][j]; //delete
int y=1+edit[i][j-1]; //insert
int z=1+edit[i-1][j-1]; //replace
edit[i][j]=min(x,min(y,z));
}
}
}
//now, return the final value
return edit[len1][len2];
}
int main()
{
string src,dest;
cout<<"Enter source string ";
getline(cin, src);
cout<<"Enter destination string ";
getline(cin, dest);
int len1=src.length(); //length of src string
int len2=dest.length(); //length of dest string
cout<<"Minimum number of edit operations required for transforming \nsource string to destination string is "<<minEditDistance(src,dest,len1,len2);
cout<<endl;
return 0;
}
In the main function, we ask the user to input the source and destination strings. We pass these values to the function minEditDistance as parameters. This function will calculate the expected result and return it. The returned value will be displayed.
Case-1: $ g++ edit_distance_DP.cpp $ ./a.out Enter source string vish Enter destination string vishal Minimum number of edit operations required for transforming source string to destination string is 3
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Apply for Data Structure Internship
- Practice Programming MCQs
- Buy Computer Science Books
- Buy Data Structure Books
- Apply for Information Technology Internship