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

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            String firstStr = scanner.nextLine();
            String secondStr = scanner.nextLine();
            int firstLength = firstStr.length();
            int secondLength = secondStr.length();
            int[][] dp = new int[firstLength + 1][secondLength + 1];
            dp[0][0] = 0;
            //secondStr只有0个字符时，初始化从secondStr变为firstStr时需要的最少的编辑次数,通过添加的形式
            for(int i = 1;i <= firstLength; i ++)
            {
                dp[i][0] = i;
            }
            //firstStr只有0个字符时，初始化从secondStr变为firstStr时需要的最少的编辑次数，通过删除的形式
            for(int j = 1;j <= secondLength; j ++)
            {
                dp[0][j] = j;
            }

            //因为至少有1个字符，所以从下标1开始
            for(int i = 1; i <= firstLength; i ++)
            {
                for(int j = 1; j <= secondLength; j ++)
                {
                    //情形1：firstStr有i-1个字符，secondStr有j个字符，转为一样需要的最小编辑次数为dp[i - 1][j]，
                    //为什么要加1？ firstStr现在为i个字符，secondStr为j个字符，转为一样可以有如下方法(不管哪一种操作，需要的编辑次数都为1)
                    // 1. firstStr去掉第i个字符，编辑次数为1
                    // 2. secondStr添加第i个字符，编辑次数为1
                    int val1 = dp[i - 1][j] + 1;
                    int val2 = dp[i][j - 1] + 1;
                    int val3 = dp[i - 1][j - 1];
                    //比较firstStr的第i个字符和secondStr的第j个字符是否相等，请注意下标(i-1)才是第i个字符
                    if(!(firstStr.charAt(i - 1) == secondStr.charAt(j - 1)))
                    {
                        val3 = val3 + 1;
                    }
                    //取val1，val2,val3三者最小值，即：firstStr有i个字符，secondeStr有j个字符，它们转为相同时所需要的最小编辑次数
                    dp[i][j] = Math.min(Math.min(val1,val2),val3);
                }
            }
            System.out.println(dp[firstLength][secondLength]);
        }
    }
}