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

没想出来，参考其他人代码

import java.util.Scanner;

/**
 * 【计算字符串的编辑距离】
 *
 *  描述：
 *  Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。
 *  许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
 *  编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
 *
 * 例如：
 * 字符串A: abcdefg
 * 字符串B: abcdef
 *
 * 通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
 *
 * 要求：
 * 给定任意两个字符串，写出一个算法计算它们的编辑距离。
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String firstLine = sc.nextLine();
        String secondLine = sc.nextLine();

        char[] first = firstLine.toCharArray();
        char[] second = secondLine.toCharArray();
        // 规划数组
        int[][] dp = new int[first.length + 1][second.length + 1];

        for (int i = 0; i <= second.length; i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i <= first.length; i++) {
            dp[i][0] = i;
        }

        for (int i = 1; i <= first.length; i++) {
            for (int j = 1; j <= second.length; j++) {
                int top = dp[i - 1][j];
                int left = dp[i][j - 1];

                if (first[i - 1] == second[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    top++;
                    left++;
                    dp[i][j] = Math.min(Math.min(top, left), dp[i - 1][j - 1] + 1);
                }
            }
        }
        System.out.println(dp[first.length][second.length]);
    }
}