import java.util.Scanner;

public class Main {
    public static int calDistance(String str1, String str2){
        int m = str1.length();
        int n = str2.length();

        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(str1.charAt(i - 1) == str2.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 - 1][j], dp[i][j - 1])) + 1;
            }
        }
        return dp[m][n];
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        System.out.println(calDistance(s1, s2));
    }
}

Levenshtein Distance (编辑距离) 算法笔记

1. 基本概念

编辑距离是指两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。允许的编辑操作包括：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

2. 动态规划解法

2.1 定义状态

使用二维数组 dp，其中：

  • dp[i][j] 表示字符串 A 的前 i 个字符和字符串 B 的前 j 个字符之间的编辑距离

2.2 初始化

// 当字符串B为空时
for(int i=0; i<=m; i++) 
    dp[i][0] = i;  // 需要删除i个字符

// 当字符串A为空时  
for(int j=0; j<=n; j++)
    dp[0][j] = j;  // 需要插入j个字符

2.3 状态转移方程

if(A.charAt(i-1) == B.charAt(j-1)) {
    dp[i][j] = dp[i-1][j-1];  // 字符相同，无需操作
} else {
    dp[i][j] = min(
        dp[i-1][j] + 1,    // 删除A[i]
        dp[i][j-1] + 1,    // 在A中插入B[j] 
        dp[i-1][j-1] + 1  // 替换A[i]为B[j]
    );
}

2.4 图解示例

Levenshtein Distance 计算示例：kitten → sitting

动态规划表格

计算过程解析

  1. 初始化：第一行：空字符串 → "sitting" 需要 7 次插入操作第一列："kitten" → 空字符串需要 6 次删除操作
  2. 填充规则：当字符匹配时：dp[i][j] = dp[i-1][j-1]当字符不匹配时：dp[i][j] = min(左+1, 上+1, 左上+1)
  3. 关键计算点：dp[1][1] (k→s): min(0+1, 1+1, 1+1) = 1 (替换)dp[2][2] (i→i): = dp[1][1] = 1 (相同)dp[5][5] (e→i): min(2+1, 2+1, 3+1) = 3 → 实际取 2 (为什么？)

最优编辑路径

从右下角 dp[6][7]=3 回溯：

  1. g≠n → 替换（3←4）
  2. n=n → 保持（4←3）
  3. i≠e → 替换（3←2）
  4. t=t → 保持（2←1）
  5. t=t → 保持（1←1）
  6. i≠k → 替换（1←0）

实际编辑操作

  1. k → s (替换)
  2. 保留 i
  3. 保留 t
  4. 保留 t
  5. e → i (替换)
  6. 保留 n
  7. 插入 g

总编辑距离：3 次操作

  • 2 次替换（k→s, e→i）
  • 1 次插入（末尾加g）

复杂度验证

对于 m=6 (kitten), n=7 (sitting):

  • 时间复杂度：6×7=42 次计算
  • 空间复杂度：6×7=42 个存储单元