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.

source Code

package com.dsacode.Algorithm.dynamic;
 
public class EditDistance {
 
    public static int getEditDistance(String a, String b) {
        int m = a.length();
        int n = b.length();
        int[][] len = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
          len[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
          len[0][j] = j;
        }
        for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) {
            if (a.charAt(i) == b.charAt(j)) {
              len[i + 1][j + 1] = len[i][j];
            } else {
              len[i + 1][j + 1] = 1 + Math.min(len[i][j], Math.min(len[i + 1][j], len[i][j + 1]));
            }
          }
        }
        return len[m][n];
      }
 
     
      public static void main(String[] args) {
        String a = "helloworld";
        String b = "owo";
        System.out.print("Edit distance  between '"+ a +"' and '"+b +"' is ");
        System.out.print(getEditDistance(a, b));
      }
 
}

Output

Edit distance between 'helloworld' and 'owo' is 7

Algorithm Explanation

	Pass arguments to the utility function.
	Search a path from the start string to the final str.
	Create a new array with the total length of two strings.
	Iterate the string and check last char. If last two chars equal, update dp value for +1 length.
	Return the value and print the string.

Time Complexity

Reference

1. https://en.wikipedia.org/wiki/Edit_distance
2. https://web.stanford.edu/class/cs124/lec/med.pdf
3. http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/