public class MinimumEditDistance {

    public static int editDistance(char[] X, char[] Y, int m, int n) {
        if (m==0) {
            return n;  // insert all n characters of Y
        }
        if (n==0) {
            return m;   // insert all m characters of X
        }
        if (X[m-1]==Y[n-1]) {
            return editDistance(X, Y, m-1, n-1);       // no change
        }
        return 1 + Math.min(editDistance(X, Y, m, n-1),    // insert Y[n-1]
                Math.min(editDistance(X, Y, m-1, n),       // delete X[m-1]
                        editDistance(X, Y, m-1, n-1))); // replace X[m-1] by Y[n-1]
    }


    public static void executeTest(String x, String y) {
        char[] X = x.toCharArray();
        char[] Y = y.toCharArray();
        int m = X.length;
        int n = Y.length;

        System.out.println("Computing Minimum edit distance for:");
        System.out.println(x);
        System.out.println(y);

        long start = System.currentTimeMillis();
        int dist = editDistance(X, Y, m, n);
        long end = System.currentTimeMillis();

        System.out.println("Computation time =" + (end - start) + " ms");
        System.out.println("Minimum edit distance: " + dist);
    }

    public static void main(String[] args) {
        executeTest("intention", "execution");
        executeTest("algorithmic", "altruistic");
        executeTest("to be or not", "tobias notes");
        executeTest("to be or not to be", "tobias not tom");// this one takes very long!
        // executeTest("to be or not to be", "to live or not to live");
 
       // improve editDistance  by Dynamic Programming techniques 
       // such that you can run the last tests 
    }
}