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

import java.util.Scanner;

/**
 * 解题思路:
 * 首先对于修改字符串子类的题,第一时间应该想到动态规划
 * 首先我们假定是将 A 编辑为 B
 * 因此要将 A[0,...i-1] 编辑为 B[0,...j-1] 有如下两种情况
 * 1. A[i-1] == B[j-1]
 * 显而易见 A[0,...i-1] 编辑为 B[0,...j-1] == A[0,...i-2] 编辑为 B[0,...j-2]
 * 2. A[i-1] != B[j-1] (这个情况下又分为三种情况)
 * (1)插入: A[0,...i-1] 编辑为 B[0,...j-2], 再插入 B[j-1]
 * (2)删除: A[0,...i-2] 编辑为 B[0,...j-1], 再删除 A[i-1]
 * (3)修改: A[0,...i-2] 编辑为 B[0,...j-2], 再将 A[i-1] 修改为 B[j-1]
 */
public class Main {
    /**
     * 根据上面的解题思路,我们有如下定义
     * 状态定义: dp[i][j] 为 A 的前 i-1 个字符转换为 B 的前 j-1 个字符的最小编辑距离
     * 转移方程:
     * 当 A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1]
     * 当 A[i-1] != B[j-1]: dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) + 1
     * 初始值: 初始化 dp 的第一行和第一列
     * 返回值: 返回 dp[i][j] 即可
     * @param args
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String A = scanner.nextLine();
            String B = scanner.nextLine();
            int lenA = A.length();
            int lenB = B.length();
            //状态数组
            int[][] dp = new int[lenA+1][lenB+1];
            //初始化
            for (int i = 0; i <= lenA; i++) {
                dp[i][0] = i;
            }
            for (int i = 0; i <= lenB; i++) {
                dp[0][i] = i;
            }
            //状态转移
            for (int i = 1; i <= lenA; i++) {
                for (int j = 1; j <= lenB; j++) {
                    if (A.charAt(i-1) == B.charAt(j-1)) {
                        dp[i][j] = dp[i-1][j-1];
                    } else {
                        dp[i][j] = Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1])) + 1;
                    }
                }
            }
            System.out.println(dp[lenA][lenB]);
        }
    }
}