**Edit Distance Problem Statement:**

*Given two stings, String A and String B, we need to convert A to B in minimum number of steps possible. The following 3 options are allowed:*

*Insert a character.**Delete a character.**Replace a character.*

All the three operations are assumed to equal amount of time ( say 1 unit).

**Edit Distance Examples:**

**Insertion:**String A= “Hell” , String B =”Hello”

Here we just need to add ‘o’ to the end of the string A.

So minimum operations required are : 1.**Deletion:**String A=”swaggy”, String B=”swag”

Here we just need to delete ‘g’ and ‘y’ from A to make it B.

So, minimum operations required are : 2.**Replacement:**String A=”Cat” ,String B=”Gap”

Here we need to replace the ‘t’ with ‘p’ and ‘C’ with ‘G’.

So, minimum operations required are : 2.

**Edit Distance Solution:**

Here, the answer to a bigger problem can be derived from smaller sub-problem using DP.

The idea is to start from right side of string A and String B (Let M and N be the respective string lengths) and then make required changes using the following two points :

- If the
**Last character are Same,**we ignore them and recur calculate the answer for strings of length M-1 and N-1. - If they are different, then we consider the following 3 sub-problems, take their minimum and add 1 to get the answer:
- Insertion of last character: Recur for M and N-1.
- Deletion of last character: Recur for M-1 and N.
- Replacement of last character: Recur for M-1 and N-1.

**Edit Distance State of DP: **

**E[i,j] **denotes the minimum moves required to convert A[1 to i] (means first i character of String A) to B[1 to j] .

**Edit Distance Recursion:**

* E[i,j] = min{ E[i][j-1] , E[j-1][i] , E[i-1,j-1] +diff(i,j)}* where

diff(i,j) = 1 if A[i]!=B[j]

= 0 if A[i]=B[j]

Here are the videos that explain by taking an example:

Here is the working code:

#include<bits/stdc++.h> using namespace std; int EditDistance( string A , string B , int n ,int m){ /*An extra row and column has been included to take care of the cases when either of the sritng is of length 0*/ int E[n+1][m+1]; int i,j; for( i=0;i<=n;i++){ for(j=0;j<=m;j++){ /*String A is empty, Only way is to Insert everything*/ if( i==0) E[i][j]=j; /*String B is empty, Only way is to Delete everything*/ else if(j==0) E[i][j]=i; /*If the last character is same*/ else if( A[i-1]==B[j-1]) E[i][j] = E[i-1][j-1]; /*If the last character is different*/ else { E[i][j] = min( E[i][j-1],min( E[i-1][j], E[i-1][j-1]))+1; } } } return E[n][m]; } int main() { string A = "Cloud Kaksha"; string B = "Code Kaksha"; cout<<"The Answer for this conversion is\n"; cout<<EditDistance( A , B , A.length(),B.length()); return 0; }

**Output:**

The Answer for this conversion is 3

**Time Complexity: O(M*N)
Auxiliary Space: O(M*N)**

An application of this algorithm is the Spoj EDIST question. To understand how solution works, read the question and then refer to Spoj EDIST solution.