# Edit Distance-dynamic programming

Given two strings s1 and s2 and below operations that can performed on s1. Find minimum number of edits (operations) required to convert ‘s1′ into ‘s2′.

Insert

Remove

Replace

All of the above operations are of cost=1.

Both the strings are of lowercase.

example:

s1=abcdef

s2=azced

s1 into s2 will take min of

first replace b to z

second delete d

third replace f to d

c++ implementation using dynamic programming:

y is no of test cases:

Insert

Remove

Replace

All of the above operations are of cost=1.

Both the strings are of lowercase.

example:

s1=abcdef

s2=azced

s1 into s2 will take min of

**3**cost, therefore answer is 3.first replace b to z

second delete d

third replace f to d

c++ implementation using dynamic programming:

y is no of test cases:

**#include <iostream>
using namespace std;
void edit(string s1,string s2,int n,int w)
{
int t[n+1][w+1];
for(int i=0;i<=n;i++)
t[i][0]=i;
for(int j=0;j<=w;j++)
t[0][j]=j;
//comparing that particular value here s1[i-1] and s2[j-1] because of zero indexing
for(int i=1;i<=n;i++)
{
for(int j=1;j<=w;j++)
{
if(s1[i-1]==s2[j-1])
t[i][j]=t[i-1][j-1];
else
{
int x=min(t[i-1][j],t[i][j-1]);
t[i][j]=min(x,t[i-1][j-1])+1;
}
}
}
//max value will b present in last cell
cout<<t[n][w];
}
int main() {
int y; cin>>y;
while(y--)
{ int n; int w;
cin>>n>>w;
string s1;
string s2;
cin>>s1>>s2;
edit(s1,s2,n,w);
cout<<endl;
}
return 0;
}**