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

// mark
// 参考：https://www.cnblogs.com/yulinfeng/p/7096882.html 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String a = in.nextLine();
            String b = in.nextLine();
            int length1 = a.length();
            int length2 = b.length();
            int[][] dp = new int[length1 + 1][length2 + 1];
            for (int i = 1; i < length1 + 1; i++) {
                dp[i][0] = i;
            }
            for (int j = 1; j < length2 + 1; j++) {
                dp[0][j] = j;
            }
            for (int i = 1; i < length1 + 1; i++) {
                for (int j = 1; j < length2 + 1; 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, 
                            Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));
                    }
                }
            }
            System.out.println(dp[length1][length2]);
        }
    }
}