[Solved] You are given two strings str1 and str2. Find the minimum number of edits (operations) that can be performed on str1 to transform it into str2 with Java

You are given two strings str1 and str2. Find the minimum number of edits (operations) that can be performed on str1 to transform it into str2. The operations that can be performed on str1 are :-
1. Insert – You can insert a character anywhere in str1.
2. Remove – You can remove any character from str1.
3. Replace – You can replace any character from str1 with any other character.

All of the above operations are of equal cost.

Suppose str1 = abcd and str2 = abfde, then the minimum number of edits required will be 2(Replace ‘c’ with ‘f’ and insert ‘e’ at the end)

Input:

4
abcd
5
abfde

Output:

2

Solution

import java.util.*;
class myp 
{
  public static void main (String[] args) 
  {
    Scanner sc =  new Scanner(System.in);
    int m=sc.nextInt();
    String str1=sc.next();
    int n=sc.nextInt();
    String str2=sc.next();	       
    int t1=editDist(str1, str2, m, n);
    System.out.println(t1);
  }
  public static int editDist(String str1, String str2, int m, int n)
  {
    //write your code here
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        if (i == 0) {
          dp[i][j] = j;
        //sauravhathi
        } else if (j == 0) {
          dp[i][j] = i;
        } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
        //sauravhathi
          dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
        }
      }
    }
    return dp[m][n];
  }
}

Happy Learning – If you require any further information, feel free to contact me.