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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //读入数据
        char[] str1 = sc.nextLine().toCharArray();
        char[] str2 = sc.nextLine().toCharArray();
        int[][] L = new int[str2.length+1][str1.length+1];
        //初始化二维数组
        for (int j = 0; j <= str2.length; j++) {
            L[j][0] = j;//每一行的开头
        }
        for (int i = 0; i <= str1.length; i++) {
            L[0][i] = i;//每一列的开头
        }
        //状态方程
        for (int i = 1; i <= str1.length; i++) {//列
            for (int j = 1; j <= str2.length; j++) {//行
                 /*值不相同时，三选一，选择最小值。
                L[i][j]=L[i-1][j]+1    在i-1的位置的基础上， 替换i-1的位置成为相同的值。 +1的意思是  替换的这一步。
                L[i][j]=L[i][j-1]+1    在j-1的位置的基础上， 替换j-1的位置成为相同的值。 一步
                L[i][j]=L[i-1][j-1]+1  在i-1和j-1的位置的基础上，替换i-1或j-1的位置的值，让他们相同。 一步
                */
                L[j][i] = Math.min((Math.min(L[j][i-1],L[j-1][i])),L[j-1][i-1]);
                if(str1[i-1] == str2[j-1]){
                    //L[j][i] = L[j][i];//为什么不是这个？？？而是下面的。
                    L[j][i] = L[j-1][i-1];//?因为这个位置，代表的是没有加上i和j之前的最小值的比较结果。所以相同时，就等于他就好。
                }else if(str1[i-1] != str2[j-1]){
                    L[j][i] = L[j][i] + 1;
                }
            }
        }
        System.out.println(L[str2.length][str1.length]);
    }
    
}



/*
ucyfsmg
zuixhuhyjgksyhqkjqxwylkoubykjxtcvkyqjpzgltbemmbmqibxxqpkgbvwbmjotixanvciibubglizmumcrjavakiygyuv
91

zikwvkijajpkaicihcffiemzexmwjjlyrylxcuoewdmpivudhmgkuodjaurazdjnlgtpwz
wpnmubqfsnmapqpufmmsphqehjplwjkqspnnpywsvvjilxbcfsrygbelquaalenvkruyltiwqcpdrxgstywaja

73

具体解题思路： 超级推荐！！！
信息学奥赛 1298-计算字符串距离_哔哩哔哩_bilibili
https://www.bilibili.com/video/BV1r64y1Q7pJ/?from=search&seid=15710822689247570421&spm_id_from=333.337.0.0&vd_source=f942daf4edf475e6f5555e2b144929a2

*/