72. Edit Distance

Algorithm

• Create a 2D array lookup[i][j]. It's defined as Minimum edit distance between substring of one input string with index from 0 to i - 1 and substring of another input string with index from 0 to j - 1.
• for lookup[i][j]
  • if a[i - 1] == b[j - 1], we can ignore these two characters and recur for remaining string.
  • if a[i - 1] != b[j - 1], consider three operations to make them same and find minimum.

Code

public class EditDistance {
    private int[][] lookupRecursive;
    public int editDistRecursive(String word1, String word2) {
        char[] a = word1.toCharArray();
        char[] b = word2.toCharArray();
        lookupRecursive = new int[a.length + 1][b.length + 1];
        for (int i = 0; i <= a.length; i++) {
            for (int j = 0; j <= b.length; j++) {
                lookupRecursive[i][j] = -1;
            }
        }
        return helper(a, b, a.length, b.length);
    }

    private int helper(char[] a, char[] b, int lengthA, int lengthB) {
        if (lookupRecursive[lengthA][lengthB] == -1) {
            if (lengthA == 0) {
                lookupRecursive[lengthA][lengthB] = lengthB;
            } else if (lengthB == 0) {
                lookupRecursive[lengthA][lengthB] = lengthA;
            } else if (a[lengthA - 1] == b[lengthB - 1]) {
                lookupRecursive[lengthA][lengthB] = helper(a, b, lengthA - 1, lengthB - 1);
            } else {
                lookupRecursive[lengthA][lengthB] = min(helper(a, b, lengthA - 1, lengthB - 1), // replace
                                                        helper(a, b, lengthA, lengthB - 1), // insert
                                                        helper(a, b, lengthA - 1, lengthB)) + 1; // remove
            }
        }
        return lookupRecursive[lengthA][lengthB];
    }

    private int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }

    public int editDistIterative(String word1, String word2) {
        char[] a = word1.toCharArray();
        char[] b = word2.toCharArray();
        int[][] lookupIterative = new int[a.length + 1][b.length + 1];
        for (int i = 0; i <= a.length; i++) {
            for (int j = 0; j <= b.length; j++) {
                if (i == 0) {
                    lookupIterative[i][j] = j;
                } else if (j == 0) {
                    lookupIterative[i][j] = i;
                } else if (a[i - 1] == b[j - 1]) {
                    lookupIterative[i][j] = lookupIterative[i - 1][j - 1];
                } else {
                    lookupIterative[i][j] = min(lookupIterative[i - 1][j - 1], // replac
                                          lookupIterative[i][j - 1], // insert
                                          lookupIterative[i - 1][j]) + 1; // delete
                }
            }
        }
        return lookupIterative[a.length][b.length];
    }
}