Edit distance

Edit distance is a way of quantifying how dissimilar two strings are to one another by counting the minimum number of operations required to transform one string into the other.

Write a program to find the minimum edit distance between two strings.

Algorithm Explanation

	Pass two strings to the utility function.
	Create new array using the total length of two strings.
	Iterate the string and check last char. If last two chars equal, update the value with +1 length
	Return the value and print the string.

Source Code

package com.dsacode.DataStructre.array;
 
public class EditDistance {
 
    public  int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
      
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
      
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
      
        for (int i = 0; i < len1; i++) {
            char c1 = word1.charAt(i);
            for (int j = 0; j < len2; j++) {
                char c2 = word2.charAt(j);
      
                if (c1 == c2) {
                    dp[i + 1][j + 1] = dp[i][j];
                } else {
                    int replace = dp[i][j] + 1;
                    int insert = dp[i][j + 1] + 1;
                    int delete = dp[i + 1][j] + 1;
      
                    int min = replace > insert ? insert : replace;
                    min = delete > min ? min : delete;
                    dp[i + 1][j + 1] = min;
                }
            }
        }
      
        return dp[len1][len2];
    }
     
    public static void main(String[] args) {
        String str = "Hello world";
        String dis= "world";
        EditDistance e = new EditDistance();
        System.out.println("Minimum distance between  '"+ str +"' and '"+ dis +"' : "+e.minDistance(str,dis));
 
    }
 
}

Output

Minimum distance between 'Hello world' and 'world' : 6