递归方法中的冗余返回问题：编辑距离递归代码优化求助

嘿，我来帮你拆解这段代码里的问题，以及给出对应的优化思路～

首先说说你代码里的冗余返回问题 #

1. 错误且冗余的初始判断逻辑 #

你代码里的第一个if条件：

if((s2.isEmpty() && (dn == 0 && dc == 0 && di == 0)) || (s1.isEmpty() && (dn == 0 && dc == 0 && di == 0))) 
    return Integer.max(s1.length(), s2.length());

这个判断完全不符合编辑距离的核心逻辑，而且属于冗余拦截：

• 首先，dn == 0 && dc == 0 && di == 0意味着所有合法操作都被禁用，这种情况下除非s1和s2完全一致，否则根本无法完成转换，返回max(s1.length(), s2.length())是错误的（应该返回无穷大或者抛出异常表示无法完成）。
• 其次，这个条件会提前拦截正常的递归终止路径，比如当s2为空但允许插入操作时，原本应该返回s1.length()（需要插入这么多字符），但这个条件会错误地返回max值，导致结果完全偏离预期。

2. 递归子问题的重复计算（核心冗余） #

这是递归实现编辑距离的经典问题：没有对已经计算过的子问题结果进行缓存。比如当你多次递归调用editDistance(s1.substring(1), s2.substring(1))、editDistance(s1, s2.substring(1))等相同参数的子问题时，每次都会重新计算一遍，时间复杂度会飙升到O(3^min(m,n))（m、n是两个字符串的长度），当字符串稍长时，性能会急剧下降。

优化方案 #

1. 修复终止条件，移除冗余判断 #

先把错误的初始判断删掉，替换成编辑距离的标准终止逻辑：

• 当s2为空时，要把它转成s1，需要插入s1.length()个字符，直接返回这个值
• 当s1为空时，要把s2转成s1，需要删除s2.length()个字符，直接返回这个值

2. 增加记忆化（Memoization）缓存 #

用一个二维数组或者HashMap来存储已经计算过的子问题结果，避免重复计算。这里推荐用二维数组，因为字符串的长度是固定的，索引访问更高效。

3. 优化字符串传递方式（可选但推荐） #

每次调用substring会创建新的字符串对象，带来额外的性能开销。可以改用传递索引的方式，记录当前处理到s1的第i位和s2的第j位，避免字符串拷贝。

优化后的代码示例 #

下面是带记忆化的递归实现，用索引+二维数组缓存：

private static int editDistance(String s1, String s2) {
    // 创建二维缓存数组，存储已经计算过的子问题结果
    Integer[][] memo = new Integer[s1.length() + 1][s2.length() + 1];
    return editDistanceHelper(s1, s2, 0, 0, memo);
}

private static int editDistanceHelper(String s1, String s2, int i, int j, Integer[][] memo) {
    // 终止条件：s2已经处理完，需要插入s1剩下的所有字符
    if (j == s2.length()) {
        return s1.length() - i;
    }
    // 终止条件：s1已经处理完，需要删除s2剩下的所有字符
    if (i == s1.length()) {
        return s2.length() - j;
    }

    // 如果已经计算过当前子问题，直接返回缓存结果
    if (memo[i][j] != null) {
        return memo[i][j];
    }

    int result;
    // 当前字符相同，不需要操作，直接递归处理下一位
    if (s1.charAt(i) == s2.charAt(j)) {
        result = editDistanceHelper(s1, s2, i + 1, j + 1, memo);
    } else {
        // 三种操作的选择：
        int delete = 1 + editDistanceHelper(s1, s2, i, j + 1, memo); // 删除s2的当前字符
        int insert = 1 + editDistanceHelper(s1, s2, i + 1, j, memo); // 在s2插入当前s1的字符
        // 取最小的操作次数
        result = Math.min(delete, insert);
    }

    // 缓存当前子问题的结果
    memo[i][j] = result;
    return result;
}

额外说明 #

如果你的场景确实需要禁用某些操作（比如不允许插入/删除），可以在对应的分支里跳过该操作，比如禁用插入的话，就只计算删除和不操作的情况，但要确保逻辑自洽（比如禁用所有操作时，只有当s1和s2完全相同时返回0，否则返回无穷大）。

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