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 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:
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;
}