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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.nextLine();
        String b = in.nextLine();
        int[][] dp = new int[a.length() + 1][b.length() + 1];
        // 初始化 当b串为空串时 a串的编辑距离 为a串的长度
        for (int i = 1; i <= a.length(); i++) {
            dp[i][0] = i;
        }        
        for (int i = 1; i <= b.length(); i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                // 如果当前位置两个字符相等 那么不用编辑 
                // 编辑距离等于前一个字符的编辑距离
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 在替换、插入、删除中找一个最小的编辑距离
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, 
                        Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        System.out.println(dp[a.length()][b.length()]);
    }
}