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

import java.util.*;
import java.math.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        //第一行字符串
        String s1 = in.nextLine();
        //第二行字符串
        String s2 = in.nextLine();
        int len1 = s1.length();
        int len2 = s2.length();
        //如果有一个字符串长度为0，则返回另外一个字符串长度
        if(len1 * len2 == 0){
            System.out.print(len1 + len2);
            return;
        }
        //构建二维数组
        int[][] dp = new int[len1 + 1][len2 + 1];
        //添加减法边界条件
        for(int i = 0; i <= len1; i++){
            dp[i][0] = i;
        }
        //添加加法边界条件
        for(int j = 0; j <= len2; j++){
            dp[0][j] = j;
        }
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                }
            }
        }
        System.out.print(dp[len1][len2]);
    }
}