无删除操作的Levenshtein距离算法参数顺序敏感问题修复求助

错误原因 #

你的代码存在三个核心问题，导致参数顺序敏感：

1. 初始化与逻辑矛盾
   你在初始化第一列dp[i][0] = i时，实际表示的是通过删除操作将str1前i个字符转为空字符串的代价，但后续计算中完全移除了删除操作的选项，导致初始化逻辑和核心计算逻辑完全不匹配。

2. 缺少返回语句
   原函数声明为int类型，但没有返回dp[m][n]，属于未定义行为，输出结果可能是随机值。

3. 对称逻辑缺失
   移除删除操作后，算法仅支持通过插入和替换将str1转为str2，但反向转换时（str2转str1）可能需要删除操作才能符合你预期的规则，算法无法处理这种情况，因此结果不对称。

修正方案 #

根据你的需求，提供两种修正方向：

方案1：恢复标准Levenshtein距离（支持三个操作，对称） #

如果目标是实现标准的Levenshtein距离（对称，支持插入、删除、替换），只需补回删除操作的选项，并添加返回语句：

#include <bits/stdc++.h>
using namespace std;

int levenshteinFullMatrix(const string &str1, const string &str2) {
    int m = str1.length();
    int n = str2.length();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 初始化：第一列是删除操作代价，第一行是插入操作代价
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i; // 删除i个字符得到空串
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j; // 插入j个字符得到str2
    }

    // 核心计算：包含替换、插入、删除三个操作
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 取三个操作的最小代价+1
                dp[i][j] = min({dp[i-1][j-1], dp[i][j-1], dp[i-1][j]}) + 1;
            }
        }
    }
    return dp[m][n]; // 添加返回语句
}

int main()
{
    cout << levenshteinFullMatrix("hellox", "xhello") << endl; // 返回2（标准距离正确值）
    cout << levenshteinFullMatrix("xhello", "hellox") << endl; // 返回2（对称正确）
    return 0;
}

方案2：修正仅插入/替换的编辑距离（使其对称） #

如果你确实需要仅支持插入和替换的编辑距离，且希望结果对称，需要将两个方向的计算结果取最大值（确保满足双向转换规则）：

#include <bits/stdc++.h>
using namespace std;

int editDistanceNoDelete(const string &src, const string &dst) {
    int m = src.length();
    int n = dst.length();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 初始化：仅支持插入，非空src转空串不可行（设为无穷大）
    for (int i = 0; i <= m; i++) {
        dp[i][0] = INT_MAX;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j; // 空串转dst需要插入n次
    }

    // 核心计算：仅替换和插入
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (src[i - 1] == dst[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                int replaceCost = dp[i-1][j-1] != INT_MAX ? dp[i-1][j-1] + 1 : INT_MAX;
                int insertCost = dp[i][j-1] + 1;
                dp[i][j] = min(replaceCost, insertCost);
            }
        }
    }
    return dp[m][n];
}

// 对称化处理：取两个方向的最大值
int levenshteinFullMatrix(const string &str1, const string &str2) {
    int d1 = editDistanceNoDelete(str1, str2);
    int d2 = editDistanceNoDelete(str2, str1);
    return max(d1, d2);
}

int main()
{
    cout << levenshteinFullMatrix("hellox", "xhello") << endl; // 返回5
    cout << levenshteinFullMatrix("xhello", "hellox") << endl; // 返回5（对称正确）
    return 0;
}

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