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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 编辑距离
 * dp[i][j],表示以下标i-1结尾和以j-1结尾的字符串的编辑距离
 * 当s1[i-1]与s2[j-1]不相等时,他们有三种选择使字符串"趋于"相等,注意这里是趋于,意思是不一定一次就直接相等
 * 删除s1的最后一个字符,删除后当前结尾字符下标为i-1,j,此时编辑距离为dp[i-1][j]+1
 * 替换s1最后一个字符,替换后,该下标字符相同,消去,此时编辑距离为dp[i-1][j-1]+1
 * 增加s1末尾一个字符,增加后,该处下标相同,消去,此时编辑距离为dp[i][j-1]+1
 * 取以上最小的那个为编辑距离
 * 当相等时,编辑距离即为dp[i-1][j-1];
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        char[] s1 = br.readLine().toCharArray();
        char[] s2 = br.readLine().toCharArray();
        int[][] dp=new int[s1.length+1][s2.length+1];
        
        for (int i = 0; i <=s1.length; i++) {
            dp[i][0]=i;
        }
        for (int i = 0; i <=s2.length; i++) {
            dp[0][i]=i;
        }
        for (int i = 1; i <=s1.length; i++) {
            for (int j = 1; j <=s2.length; j++) {
                if(s1[i-1]==s2[j-1]) //字符串下标从0-(len-1)
                    dp[i][j]=dp[i-1][j-1];
                else {
                    dp[i][j] = dp[i - 1][j];
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]) + 1;
                }
            }
        }
        System.out.println(dp[s1.length][s2.length]);

    }
}