Edit distance [MEDIUM-DP] Important

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

1. Insert
2. Remove
3. Replace

All of the above operations are of cost=1.
Both the strings are of lowercase.

Company: Amazon

Input:
The First line of the input contains an integer T denoting the number of test cases. Then T test cases follow. Each tese case consists of two lines. The first line of each test case consists of two space separated integers P and Q denoting the length of the strings str1 and str2 respectively. The second line of each test case coantains two space separated strings str1 and str2 in order.

Output:
Coreesponding to each test case, pirnt in a new line, the minimum number of operations required.

Constraints:
1<=T<=50
1<= Length(str1) <= 100
1<= Length(str2) <= 100
 

Example:
Input:
1
4 5
geek gesek

Output:
1

CODE:

import java.util.*;

import java.lang.*;

import java.io.*;

class GFG {

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int m = sc.nextInt();

for(int mi=0;mi<m;mi++){

   int n1=sc.nextInt();

   int n2=sc.nextInt();

   String s1=sc.next();

   String s2=sc.next();

   System.out.println(find(n1,n2,s1,s2));

   }

}

public static int find(int n1,int n2, String s1,String s2){

   int d[][]=new int[n1+1][n2+1];

  for(int i=0;i<=n1;i++){

       for(int j=0;j<=n2;j++){

     //Boundary conditions

     if(i==0){d[i][j]=j;}

     else if(j==0){d[i][j]=i;}

     else if(s1.charAt(i-1)==s2.charAt(j-1)){d[i][j]=d[i-1][j-1];}

     else{

         d[i][j]=1+Math.min(d[i][j-1],Math.min(d[i-1][j],d[i-1][j-1]));

     }

       }

   }

   return d[n1][n2];

}

}

EXECUTION TIME:0.11s