动态编辑距离算法问题求助：计算结果与预期不符

首先得纠正一个小误解：对于字符串"casa"和"cara"，正确的编辑距离其实是1，而不是2。因为只需要把"casa"中的's'替换成'r'，就得到了"cara"——替换操作只算一次编辑，完全不需要插入加删除的组合操作。所以你的算法返回1其实是正确结果，可能你对编辑距离的定义理解有点偏差啦。

不过从你贴出的代码片段来看，里面确实存在不少问题，即使这次结果巧合正确，后续处理其他字符串大概率会出错，我帮你梳理并修正下：

代码里的明显问题 #

• 未初始化的核心变量：你声明了dp[][] = new int[m+1][n+1];，但m和n完全没赋值，应该是m = word1.length()，n = word2.length()，用来表示两个字符串的长度
• 变量名不统一：函数参数是word1和word2，但代码里却用了str1和str2，这会直接导致编译错误
• 逻辑不完整：else分支里只写了int rep=dp...，没完成关键的最小操作数计算——编辑距离需要考虑替换、删除、插入三种操作，要取这三种操作对应的dp值的最小值再加1

修正后的完整可运行代码 #

public static int distance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int dp[][] = new int[m+1][n+1];
    
    for (int i=0; i<=m; i++) {
        for (int j=0; j<=n; j++) {
            if (i == 0) {
                // 第一个字符串为空，需要插入j个字符才能匹配第二个字符串
                dp[i][j] = j;
            } else if (j == 0) {
                // 第二个字符串为空，需要删除i个字符才能匹配第一个字符串
                dp[i][j] = i;
            } else if (word1.charAt(i-1) == word2.charAt(j-1)) {
                // 当前位置字符相同，不需要额外操作，直接继承左上角的结果
                dp[i][j] = dp[i-1][j-1];
            } else {
                // 取替换、删除、插入三种操作里的最小操作数，加1表示当前这一步操作
                int replace = dp[i-1][j-1];
                int delete = dp[i-1][j];
                int insert = dp[i][j-1];
                dp[i][j] = 1 + Math.min(replace, Math.min(delete, insert));
            }
        }
    }
    return dp[m][n];
}

验证示例 #

测试"casa"和"cara"时：

• 逐个对比字符：cc，aa，s!=r，a==a
• 第三个字符不同时，取替换操作对应的dp值（dp[2][2]为0，加1后得到1），最终返回的dp[4][4]就是1，这完全符合标准编辑距离的定义。

如果你的场景是不允许使用替换操作，必须用插入+删除的组合，那可以调整else分支的逻辑，只取删除和插入的最小值加1，此时"casa"到"cara"的操作数就会是2（删除's'再插入'r'）。

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