import java.util.ArrayList;
import java.util.List;

public class MinEditDistanceOperations {

    public static int editDistance(char[] X, char[] Y, int m, int n, List<String> operations) {
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                operations.add("Insert " + Y[i]);
            }
            return n;
        }
        if (n == 0) {
            for (int i = 0; i < m; i++) {
                operations.add("Delete " + X[i]);
            }
            return m;
        }
        if (X[m - 1] == Y[n - 1]) {
            return editDistance(X, Y, m - 1, n - 1, operations);
        }
        List<String> ops1 = new ArrayList<>();
        int insertDist = editDistance(X, Y, m, n - 1, ops1); // will have to insert Y[n-1]
        List<String> ops2 = new ArrayList<>();
        int deleteDist = editDistance(X, Y, m - 1, n, ops2); // will have to delete X[m-1]
        List<String> ops3 = new ArrayList<>();
        int replaceDist = editDistance(X, Y, m - 1, n - 1, ops3); // will have to replace X[m-1] by Y[n-1]
        if (insertDist <= deleteDist && insertDist <= replaceDist) {
            operations.addAll(ops1);
            operations.add("Insert " + Y[n - 1]);
            return insertDist + 1;
        } else if (deleteDist <= insertDist && deleteDist <= replaceDist) {
            operations.addAll(ops2);
            operations.add("Delete " + X[m - 1]);
            return deleteDist + 1;
        } else {
            operations.addAll(ops3);
            operations.add("Replace " + X[m - 1] + " by " + Y[n - 1]);
            return replaceDist + 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);

        List<String> ops = new ArrayList<>();

        long start = System.currentTimeMillis();
        int dist = editDistance(X, Y, m, n, ops);
        long end = System.currentTimeMillis();
        System.out.println("Computation time =" + (end - start) + " ms");
        System.out.println("Minimum edit distance: " + dist);
        System.out.println("Operations:");
        for (String op : ops) {
            System.out.println(op);
        }
    }

    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 
    }
}