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

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            if (str1.length() < str2.length()) {
                String tmp = str1;
                str1 = str2;
                str2 = tmp;
            }
            int tmp = naxSameLen(str1, str2, 0, 0);
        
            System.out.println(tmp);
        }
    }

    public static int naxSameLen(String str1, String str2, int i1, int i2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] arr = new int[len2][len1];
        arr[0][0] = str1.charAt(0) == str2.charAt(0) ? 0 : 1;
        for (int i = 1; i < len1; i++) {
            arr[0][i] = str1.charAt(i) == str2.charAt(0) ? i : i+1;
        }
        for (int i = 1; i < len2; i++) {
            arr[i][0] = str1.charAt(0) == str2.charAt(i) ? i : i+1;
        }
        for (int i = 1; i < len2; i++) {
            for (int j = 1; j < len1; j++) {
                // if (i == j) {
                //     arr[i][j] = str1.charAt(j) == str2.charAt(i) ? arr[i-1][j-1] : arr[i-1][j-1] + 1;
                // }else {
                //     arr[i][j] = arr[i][j-1] + 1;
                // }
                int a1 = arr[i][j-1] + 1;
                int a2 = arr[i-1][j] + 1;
                int a3 = str1.charAt(j) == str2.charAt(i) ? arr[i-1][j-1] : arr[i-1][j-1] + 1;
                arr[i][j] = Math.min(a1, Math.min(a2,a3));
                
            }
        }
        return arr[len2-1][len1-1];
    }
}