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

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String s1 = in.nextLine();
            String s2 = in.nextLine();

            // 当其中一个字符串为空串时，编辑距离为另一字符串长度
            // dp[i][j]：s1的前i个字符与s2的前j个字符所需要的编辑距离
            int dp[][] = new int[s1.length() + 1][s2.length() + 1];

            // 其中一个字符串为空串时初始化
            for(int i = 0;i <= s1.length();i++){
                dp[i][0] = i;
            }

            for(int j = 0;j <= s2.length();j++){
                dp[0][j] = j;
            }

            for(int i = 1;i <= s1.length();i++){
                for(int j = 1;j <= s2.length();j++){
                    // 状态转移
                    // 1、当s1的第i个字符与s2的第j个字符相等时。不需要编辑即编辑距离为dp[i -1][j -1]
                    if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                        dp[i][j] = dp[i - 1][j - 1];
                    }else{
                        // 2、当所在对应位置字符不相等时
                        // 替换字符串b，编辑距离为dp[i-1][j-1]+1
                        // 插入一个字符与其相等，则编辑距离为dp[i-1][j]+1；
                        // 删除该字符，编辑距离为dp[i][j-1]+1，三者取其小即可
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1],dp[i - 1][j]),dp[i][j - 1]) + 1;
                    }
                }
            }
            System.out.println(dp[s1.length()][s2.length()]);
        }
    }
}