Java编辑距离算法问题：计算插入删除次数总和失效求助

嘿，我瞅了下你的递归算法，发现几个关键问题导致它跑不起来，咱们一步步来捋清楚并修复：

1. 核心问题点拆解 #

你的代码不仅没写完（int rep = ...后面截断了），还存在几个逻辑错误：

• 终止条件完全写反：当遍历完s1时，你需要插入s2中剩下的所有字符，所以应该返回s2.length() - j，而不是j；同理遍历完s2时，要删除s1剩余的字符，应该返回s1.length() - i，不是i。
• 错误引入了替换分支：你的需求是统计插入和删除的操作次数之和，替换操作本质是删除+插入（次数为2），不属于这个范畴，所以这个分支应该直接去掉。
• 递归分支缺失：当字符不相等时，你需要考虑两种合法操作：删除s1当前字符，或者插入s2当前字符，然后取这两个分支里的最小操作次数。

2. 修正后的基础递归版本 #

先给你修复好的基础递归代码：

public static int distance(String s1, String s2) {
    return distance(s1, s2, 0, 0);
}

private static int distance(String s1, String s2, int i, int j) {
    // 终止条件1：s1遍历完，需要插入s2剩余的所有字符
    if (i == s1.length()) {
        return s2.length() - j;
    }
    // 终止条件2：s2遍历完，需要删除s1剩余的所有字符
    if (j == s2.length()) {
        return s1.length() - i;
    }
    // 当前字符相等，不需要操作，直接递归下一组字符
    if (s1.charAt(i) == s2.charAt(j)) {
        return distance(s1, s2, i + 1, j + 1);
    }
    // 字符不相等，两种选择：删除s1当前字符 或 插入s2当前字符，取最小次数
    int deleteOp = distance(s1, s2, i + 1, j) + 1;
    int insertOp = distance(s1, s2, i, j + 1) + 1;
    return Math.min(deleteOp, insertOp);
}

3. 优化：记忆化递归（避免重复计算） #

上面的基础递归会有大量重复的子问题（比如多次计算同一个i,j的情况），效率很低。我们可以用二维数组缓存已经计算过的结果：

import java.util.Arrays;

public static int distance(String s1, String s2) {
    // 创建记忆化缓存，初始值-1表示未计算
    int[][] memo = new int[s1.length() + 1][s2.length() + 1];
    for (int[] row : memo) {
        Arrays.fill(row, -1);
    }
    return distanceMemo(s1, s2, 0, 0, memo);
}

private static int distanceMemo(String s1, String s2, int i, int j, int[][] memo) {
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    if (i == s1.length()) {
        memo[i][j] = s2.length() - j;
        return memo[i][j];
    }
    if (j == s2.length()) {
        memo[i][j] = s1.length() - i;
        return memo[i][j];
    }
    if (s1.charAt(i) == s2.charAt(j)) {
        memo[i][j] = distanceMemo(s1, s2, i + 1, j + 1, memo);
        return memo[i][j];
    }
    int deleteOp = distanceMemo(s1, s2, i + 1, j, memo) + 1;
    int insertOp = distanceMemo(s1, s2, i, j + 1, memo) + 1;
    memo[i][j] = Math.min(deleteOp, insertOp);
    return memo[i][j];
}

4. 更高效的迭代DP版本 #

对于长字符串，递归可能会触发栈溢出，推荐用动态规划的迭代版本：

public static int distanceDP(String s1, String s2) {
    int m = s1.length();
    int n = s2.length();
    // dp[i][j]表示s1前i个字符转成s2前j个字符的最小插入删除次数
    int[][] dp = new int[m + 1][n + 1];
    
    // 初始化：s1为空时，需要插入s2所有字符
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    // 初始化：s2为空时，需要删除s1所有字符
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    
    // 填充DP表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 取删除或插入的最小次数+1
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    return dp[m][n];
}

额外小知识 #

其实这个最小插入删除次数，本质等于两个字符串长度之和 - 2 * 最长公共子序列(LCS)长度。因为LCS是不需要修改的部分，剩下的s1字符要删除，剩下的s2字符要插入，总次数就是这个公式的结果，感兴趣的话也可以基于LCS来实现。

内容的提问来源于stack exchange，提问作者user9039337