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

import java.util.*;

/**
 * 难点：没思路，不知道dp[i][j]代表什么，以及如何求dp[i][j]
 * A[0,...i-1]最后修改为B[0,...j-1]，有以下两种情况：
 *      （一）A[i-1] == B[j-1]时，最后一个元素不用动，只用考虑A[0,...i-2]编辑为B[0,...j-2]需要的代价,dp[i][j] = dp[i-1][j-1]
 *      （二）A[i-1]!=B[j-1]时，又可以分成以下三种情况(以A为模板)：
 *              1、删除：从A[0,...i-2]编辑为B[0,...j-1]，再删除A[i-1]
 *              2、增加：从A[0,...i-1]编辑为B[0,...j-2]，再插入B[j-1]
 *              3、替换：从A[0,...i-2]编辑为B[0,...j-2]，再将A[i-1]修改为B[j-1]
 *      每次取三种情况最小值
 * 最后返回dp[n][m];
 * 如何初始化很重要！！！
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] A = in.nextLine().toCharArray();
        char[] B = in.nextLine().toCharArray();
        int lengthA = A.length;
        int lengthB = B.length;

        int[][] dp = new int[lengthA+1][lengthB+1];
        // dp[i][j] 表示strA 0~i-1共i个 与 strB 0~j-1共j个 的最小编辑距离
        // 如何初始化？  注意加等号
        dp[0][0] = 0;
        for (int i = 1; i <= lengthA; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= lengthB; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= lengthA; i++) {
            for (int j = 1; j <= lengthB; j++) {
                if(A[i-1] == B[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i][j-1]+1,dp[i-1][j]+1));
                }
            }
        }
        System.out.println(dp[lengthA][lengthB]);
    }
}