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:

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









darkmode