**Problem :- **

Solve the **Edit Distance** problem.

**Edit Distance** between two strings is the cost involved in converting one string to another.

For conversion, we can use three kind of operations **( INSERT, DELETE & REPLACE )**.

Assume the costs of insertion, deletion and replacing as **1**.

So, the problem is to find out minimum
number of **edits** required to convert one string to another.

For e.g, **minimum edits** required to convert **sunflower** to **sunlight** is **5**

**Solution :- **

Suppose we need to convert a string ( **str1** ) of size **m** to a string ( **str2** ) of size **n** with minimum number of edits.

First we will consider a smaller subproblem and define an optimal structure of the solution.

Let **Cost ( i , j )** denotes the minimum cost to convert first **' i '** characters of ** str1 ** to first **' j '**
characters of **str2**.

There are **2** possibilities :

**1 )** if **str1 ( i ) == str2 ( j )** , problem is reduced to finding **Cost ( i - 1 , j - 1 )** ( no edit required )

**2 )** if **str1 ( i ) != str2 ( j )** , then we can choose any of the following edit operations :

**Insert** : problem reduces to finding **Cost ( i , j - 1 ) + INSERT_COST**

i.e we insert the mismatched character and add the cost of insertion.

**Delete** : problem reduces to finding **Cost ( i - 1 , j ) + DELETE_COST**

**Replace** : problem reduces to finding **Cost ( i - 1 , j - 1 ) + REPLACE_COST**

Now, our objective is to find minimum edit cost i.e to minimize **Cost ( i , j )** . So, we will consider the minimum of the values
of above subproblems or possibilities and the optimal structure of the solution is defined as :

**Cost ( i , j ) = min [ Cost ( i , j - 1 ) + I , Cost ( i - 1 , j ) + D , Cost ( i - 1 , j - 1 ) + R ]
if str1 ( i ) != str2 ( j ) ** and

**Cost ( i , j ) = Cost ( i - 1 , j - 1 ) if str1 ( i ) == str2 ( j ) **

Now, we can find **Cost ( i , j )** for any values of **i** and **j**.

Finally, **Cost ( m , n )** gives the required minimum edit cost to convert **str1** to **str2**.

**#include<iostream>
#include<cstring>**
**#define INSERT_COST 1
#define DELETE_COST 1
#define REPLACE_COST 1**
**using namespace** std;
**int** min(**int** a,**int** b) {
**return** ((a < b) ? a : b);
}
*/* convert str1 to str2 with minimum edits(insert,delete,replace)
suppose length(str1) = m and length(str2) = n
cost(i,j) -> cost of converting str1[0...i-1] to str2[0...j-1]
cost(m,n) -> cost of converting str1 to str2
Standard recursive formula for computing cost(m,n) :-
cost(i,j) = min[cost(i-1,j)+D, cost(i,j-1)+I, cost(i-1,j-1)+R]
D -> delete cost, I -> insert cost, R -> replace cost */*
**int** editDistance(**char** str1[],**int** size1,**char** str2[],**int** size2) {
*// cost matrix
// row -> str1 & col -> str2*
**int** cost[size1][size2];
**int** i,j;
*// initialize the cost matrix*
**for** (i=0;i<size1;i++) {
**for**(j=0;j<size2;j++) {
**if** (i == 0) {
*// source string is NULL
// so we need 'j' insert operations*
cost[i][j] = j*INSERT_COST;
} **else if** (j == 0) {
*// target string is NULL
// so we need 'i' delete operations*
cost[i][j] = i*DELETE_COST;
} **else** {
cost[i][j] = -1;
}
}
} *//initialization done
//compute cost(i,j) and eventually return cost(m,n)*
**for**(i=1;i<size1;i++) {
**for**(j=1;j<size2;j++) {
**int** x = cost[i-1][j] + DELETE_COST;
**int** y = cost[i][j-1] + INSERT_COST;
*// if str1(i-1) != str2(j-1), add the replace cost
// we are comparing str1[i-1] and str2[j-1] since
// the array index starts from 0*
**int** z = cost[i-1][j-1] + (str1[i-1] != str2[j-1])*REPLACE_COST;
*// as per our recursive formula*
cost[i][j] = min(x, min(y,z));
}
}
*// last cell of the matrix holds the answer*
**return** cost[size1-1][size2-1];
}
*//main*
**int** main() {
**char** str1[] = "sunflower";
**char** str2[] = "sunlight";
**int** size1 = strlen(str1);
**int** size2 = strlen(str2);
**int** min_cost = editDistance(str1,size1+1,str2,size2+1);
cout<<"\nMinimum edits required to convert "<<str1<<
" to "<<str2<<" is "<<min_cost;
cout<<endl;
**return** 0;
}