public class EditDistance {

    public static void main(String[] args) {
        String s1 = args[0];
        String s2 = args[1];
        int [][] table = new int[s1.length()+1][s2.length()+1];
        for (int i = 0; i <= s1.length(); i++) {
            table[i][0] = i;
        }
        for (int i = 0; i <= s2.length(); i++) {
            table[0][i] = i;
        }
        for (int row = 1; row < s1.length()+1; row++) {
            char currChar = s1.charAt(row-1);
            for (int col = 1; col < s2.length()+1; col++) {
                char checkChar = s2.charAt(col-1);
                if (currChar == checkChar) {
                    table[row][col] = table[row-1][col-1];
                } else {
                    int left = table[row][col-1];
                    int up = table[row-1][col];
                    int diag = table[row-1][col-1];
                    if (left < up) {
                        if (left <= diag) {
                            table[row][col] = table[row][col-1] + 1;
                        } else {
                            table[row][col] = table[row-1][col-1] + 1;
                        }
                    } else {
                        if (up <= diag) {
                            table[row][col] = table[row-1][col] +1;
                        } else {
                            table[row][col] = table[row-1][col-1] + 1;
                        }
                    }
                }
            }
        }
        System.out.println("Edit Distance: " + table[s1.length()][s2.length()]);
    }

}