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

经典的动态规划，从 s[0~j] 串转换为 p[0~i] 串的编辑距离，有以下几种变换方式：

• 不需要变换：如果 s[j] 刚好等于 p[i]，取决于 s[0~j-1] 和 p[0~i-1] 的编辑距离，不需要修改
• 修改：如果 s[j] 不等于 p[i]，可以将 s[j] 修改为 p[i]，需要编辑一次，然后转为不需要变换的情况，所以为 s[0~j-1] 和 p[0~i-1] 的编辑距离+1
• 添加：取决于 s[0~j-1] 和 p[0~i] 的编辑距离+1
• 删除：取决于 s[0~j] 和 p[0~i-1] 的编辑距离+1

每次都在上面集中方式中取最小值，每次都可以得到最少的操作次数，也就是编辑距离。

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.hasNext()) { // 注意 while 处理多个 case
            String p = in.next();
            String s = in.next();
            // s -> p 的编辑距离
            int[][] dp = new int[p.length() + 1][s.length() + 1];
            for (int j = 1; j <= s.length(); j++) {
                dp[0][j] = dp[0][j - 1] + 1;
            }
            for (int i = 1; i <= p.length(); i++) {
                dp[i][0] = dp[i - 1][0] + 1;
                for (int j = 1; j <= s.length(); j++) {
                    // 改
                    dp[i][j] = p.charAt(i - 1) == s.charAt(j - 1) ? dp[i - 1][j - 1] : dp[i - 1][j -
                               1] + 1;
                    // 增
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
                    // 删
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
                }
            }
            System.out.println(dp[p.length()][s.length()]);
        }
    }
}