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

import java.util.Scanner;

/**
 * HJ52 计算字符串的编辑距离-中等
 */
public class HJ052 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str1 = sc.next();
            String str2 = sc.next();
            int distance = distanceStr(str1, str2);
            System.out.println(distance);
        }
        sc.close();
    }

    private static int distanceStr(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        // 初始化
        int i = 0, j = 0;
        for (i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
        // 动态规划，循环设置值
        for (i = 1; i <= len1; i++) {
            for (j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = minNum(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }

    public static int minNum(int num1, int num2, int num3) {
        int temp = Math.min(num1, num2);
        return Math.min(temp, num3);
    }
}