Edit Distance problem (dynamic programming) in C++

In this problem, we are going to learn how to change a string 1 to string 2 in C++  which is called Edit distance problem using the following operations.

• Insert
• Remove
• Replace

Using these following operations we need to convert string 1 to string 2 in minimum possible operations. The idea is simple, we need to traverse the string and need to declare a temporary array to store minimum operation till that character and we are going to use dynamic programming to solve this problem.

Let us take an example to understand the problem clearly:

Example 1:
string 1: vishu
string 2: vishal
Now we can see that first 4 characters is same. So we need to convert 'u' to 'al'.
We can replace 'u' with 'a' and insert l in string 1. So minimum operation required is 2.   

Example 2:
string 1: code
string 2: cat
We can replace 'o' with 'a' and 'd' with 't' and then we can remove 'e' from string 1.
So minimum operation required is 3.

Now let us try to implement our idea in our code.

Program to solve Edit Distance problem in C++

Cpp source code:

// Program to solve Edit distance Problem
#include<bits/stdc++.h>
using namespace std;
int editDist(string str1 , string str2 , int m ,int n,int dp[][5000]) 
{ 
    
    if (m == 0) return n; 
  
   
    if (n == 0) return m; 
  
 
    if (str1[m-1] == str2[n-1]) 
        return editDist(str1, str2, m-1, n-1,dp); 
    if(dp[m][n]!=0)
        return dp[m][n];
    else
    {
        dp[m][n]= 1 + min ( editDist(str1,  str2, m, n-1,dp),min(editDist(str1,  str2, m-1, n,dp), 
                  editDist(str1,  str2, m-1, n-1,dp))); 
        return dp[m][n];
    }
}

// Driver Program
int main()
 {
  int n,m;
  cout<<"Enter length of string 1: ";
  cin>>n;
  cout<<"\nEnter length of string 2: ";
  cin>>m;
  char a[n],b[m];
  cout<<"\nEnter string 1: ";
  for(int i=0;i<n;i++)
      cin>>a[i];
  cout<<"\nEnter string 2: ";
  for(int i=0;i<m;i++)
      cin>>b[i];
  int dp[n+1][5000];
  memset(dp,0,sizeof(dp));
  dp[0][0]=1;
        cout<<"\nMinimum operation required for conversion is "<<editDist(a,b,n,m,dp)<<"\n";
  return 0;
}

Input/Output:

Enter length of string 1: 5

Enter length of string 2: 6

Enter string 1: vishu

Enter string 2: vishal

Minimum operation required for conversion is 2

The time complexity of this code is O( length of string 1 * length of string 2).

You can also learn:

Rotate a Matrix in C++ ( Clockwise and Anticlockwise )

Longest Common Subsequence using Dynamic Programming

Do not forget to comment if you find anything wrong in the post or you want to share some information regarding the same.