public class Editointietaisyys {
    public static String a = "KØBENHAVN";
    public static String b = "KÖÖPENHAMINA";
    public static int n = a.length();
    public static int m = b.length();
    public static int[][] taulu = new int[n+1][m+1];
    public static boolean[][] valmis = new boolean[n+1][m+1];

    public static int laske(int i, int j) {
         if (i == 0) return j;
         if (j == 0) return i;
         if (valmis[i][j]) return taulu[i][j];
         int sakko = (a.charAt(i-1) == b.charAt(j-1)) ? 0 : 1;
         valmis[i][j] = true;
         taulu[i][j] = Math.min(Math.min(laske(i-1,j)+1,
                                         laske(i,j-1)+1),
                                laske(i-1,j-1)+sakko);
         return taulu[i][j];
    }

    public static void main(String[] args) {
        System.out.println("Editointietaisyys: " + laske(n, m));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                System.out.printf("%3d", taulu[i][j]);
            }
            System.out.println();
        }
    }
}
