public static int minDistance(String word1, String word2) {
char[] s1 = word1.toCharArray();
char[] s2 = word2.toCharArray();
int len1 = s1.length;
int len2 = s2.length;
int N = Math.max(len1, len2);
int[][] d = new int[N + 1][N + 1]; for (int i = 0; i <= N; i++) {
d[i][0] = i;
d[0][i] = i;
} for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1[i - 1] == s2[j - 1]) {
d[i][j] = d[i - 1][j - 1];
} else {
d[i][j] = Math.min(d[i][j - 1] + 1, Math.min(d[i - 1][j] + 1, d[i - 1][j - 1] + 1));
}
}
} for (int i = 0; i <= N; i++) {// juzheng
for (int j = 0; j <= N; j++) {
System.out.print(d[i][j]+" ");
}
System.out.println();
} return d[len1][len2];
}