题解 | #计算字符串的编辑距离#力扣的困难题

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s1 = bf.readLine();
        String s2 = bf.readLine();
        System.out.println(getLength(s1, s2));
    }

    private static int getLength(String word1, String word2) {
        //两个点
        //No.1  两个word之间不同的字母数 是最小值

        //No.2  相对顺序
        //动态规划
        int M = word1.length(), N = word2.length();

        //dp[i][j]对应什么word1的前i-1个字母和word2前j-1个字母相同的最少操作数
        int[][] dp = new int[M + 1][N + 1];
        for (int i = 1; i <= M; i++) dp[i][0] = i;
        for (int j = 1; j <= N; j++) dp[0][j] = j;

        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                //dp[i-1][j],表示第i个字符先不匹配,也可以理解为dp[i][j] = dp[i-1][j],那后面就和dp[i][j+1]比较
                //其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
                //相同则不需要操作
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //不相同                替换                删除dp[i-1][]  插入
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[M][N];
    }

}