题解 | #计算字符串的编辑距离#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String a, b;
        try {
            a = r.readLine();
            b = r.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        char[] start = a.toCharArray();
        char[] end = b.toCharArray();
        int i = 1, j, dis, row = start.length, col = end.length;
        int[][] edit = new int[row + 1][col + 1];
        while (i < col + 1) {//第一行赋初值
            edit[0][i] = i;
            i++;
        }
        i = 1;
        while (i < row + 1) {//第一列赋初值
            edit[i][0] = i;
            i++;
        }
        i = 1;
        while (i < row +
                1) {//状态转移将第一行、第一列的值，编辑后推算出矩阵其余位置的值
            j = 1;
            while (j < col + 1) {
                if (start[i - 1] == end[j - 1]) edit[i][j] = edit[i - 1][j - 1];
                else {//i行、j列不相等，则需要通过添加、修改操作变换，因为字符串是递增的，修改相当于先删除后添加，和为一步了
                    dis = Math.min(edit[i][j - 1] + 1,
                                   edit[i - 1][j] + 1);//获得左边值和上边值的最小值
                    dis = Math.min(dis, edit[i - 1][j - 1] + 1);//获得其和左上角的最小值
                    edit[i][j] = dis;//最小值赋给当前两单词的编辑距离
                }
                j++;
            }
            i++;
        }
        System.out.print(edit[row][col]);//输出最终单词的编辑距离
    }
}