Edit Distance Geeks Solution

Edit Distance Geeks Solution

  September 08, 2017    

---

Problem :

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.

InsertRemoveReplace

Idea:

We have 3 moves to do .
if two chars are same then just recur for next value
else
go with all 3 operations and find minimum value.

Code:

 public static int check(int n,int m,String a,String b)
     {
         int[][] arr=new int[n+1][m+1];
         for(int i=0;i<=n;++i)
         {
             for(int j=0;j<=m;++j)
             {
                 if(i==0)
                 arr[i][j]=j; // to convert string x- y with length 0(any) we need to add all chars.
                 else if(j==0)
                 arr[i][j]=i;
                 else if(a.charAt(i-1)==b.charAt(j-1))
                 arr[i][j]=arr[i-1][j-1];
                 else
                 arr[i][j]=1+Math.min(arr[i][j-1],Math.min(arr[i-1][j],arr[i-1][j-1]));
             }
         }
         return arr[n][m];
     }