EditDistance.java

/*
    Problem: Given two strings, find the edit distance to make those the same.
    edit - insert, remove, replace
 */
public class EditDistance 
    // complexity: time O(3^n), space O(n)
    static int findEditDistanceRecur(String X, String Y, int m, int n) {
        // base case
        if (m == 0) { // insert rest of all
            return n;
        }
        if (n == 0) { // insert rest of all
            return m;
        }

        if (X.charAt(m - 1) == Y.charAt(n - 1)) {
            return findEditDistanceRecur(X, Y, m - 1, n - 1);
        } else {
            return 1 + Math.min(
                    findEditDistanceRecur(X, Y, m, n - 1),  // insert
                    Math.min(
                    findEditDistanceRecur(X, Y, m - 1, n),  // remove
                    findEditDistanceRecur(X, Y, m - 1, n - 1))); // replace
        }
    }

    // complexity: time O(n*m), space O(n*m), m: length of X, n: length of Y
    static int findEditDistance(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[][] memo = new int[m + 1][n + 1];
        // initialize
        for (int i = 0; i <= m; i++) {
            memo[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            memo[0][i] = i;
        }

        // fill the rest
        for (int i = 1; i <= m; i++) {
            char c0 = X.charAt(i-1);
            for (int j = 1; j <= n; j++) {
                char c1 = Y.charAt(j-1);
                if (c0 == c1) {
                    memo[i][j] = memo[i-1][j-1];
                } else {
                    int replace = memo[i-1][j-1]+1;
                    int insert = memo[i][j-1] + 1;
                    int delete = memo[i-1][j] + 1;
                    memo[i][j] = Math.min(replace, Math.min(insert, delete));
                }
            }
        }
        return memo[m][n];
    }
    public static void main(String[] arg) {
        String s0 = "abcd";
        String s1 = "cdef";
        System.out.println(findEditDistanceRecur(s0, s1, s0.length(), s1.length()));
        System.out.println(findEditDistance(s0, s1));
    }
}

/*
References:
http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/
http://algorithms.tutorialhorizon.com/dynamic-programming-edit-distance-problem/
http://www.programcreek.com/2013/12/edit-distance-in-java/
https://en.wikipedia.org/wiki/Levenshtein_distance
*/