如何用C++实现字符串相似度计算的Levenshtein距离动态规划解法

Levenshtein距离又称编辑距离，指两个字符串之间，由一个转成另一个所需的最少编辑操作次数，允许的编辑操作包括将一个字符替换成另一个字符、插入一个字符、删除一个字符。在拼写纠错、DNA序列比对、搜索引擎模糊查询等场景中都有广泛应用，用动态规划实现该算法可以高效完成计算。

动态规划思路推导

要计算字符串A和字符串B的Levenshtein距离，我们可以定义一个二维数组dp，其中dp[i][j]表示A的前i个字符和B的前j个字符的编辑距离。接下来推导状态转移方程：

• 如果i为0，说明A是空字符串，要变成B的前j个字符，需要插入j次，所以dp[0][j] = j
• 如果j为0，说明B是空字符串，要删除A的前i个字符，需要删除i次，所以dp[i][0] = i
• 如果A的第i个字符和B的第j个字符相等，那么不需要额外操作，dp[i][j] = dp[i-1][j-1]
• 如果A的第i个字符和B的第j个字符不相等，我们可以选择三种操作：替换A的第i个字符为B的第j个字符，代价是dp[i-1][j-1]+1；删除A的第i个字符，代价是dp[i-1][j]+1；在A的第i个字符后插入B的第j个字符，代价是dp[i][j-1]+1，取三种情况的最小值作为dp[i][j]

完整C++实现源码

下面是Levenshtein距离动态规划解法的完整C++代码，包含输入处理和结果输出逻辑：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 计算两个字符串的Levenshtein距离
int levenshteinDistance(const string& str1, const string& str2) {
    int len1 = str1.size();
    int len2 = str2.size();
    // 定义dp数组，大小为(len1+1)*(len2+1)
    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
    
    // 初始化边界情况
    for (int i = 0; i <= len1; ++i) {
        dp[i][0] = i; // str2为空，需要删除i次
    }
    for (int j = 0; j <= len2; ++j) {
        dp[0][j] = j; // str1为空，需要插入j次
    }
    
    // 填充dp数组
    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            if (str1[i-1] == str2[j-1]) {
                // 当前字符相等，不需要额外操作
                dp[i][j] = dp[i-1][j-1];
            } else {
                // 取替换、删除、插入三种操作的最小值加1
                int replaceCost = dp[i-1][j-1] + 1;
                int deleteCost = dp[i-1][j] + 1;
                int insertCost = dp[i][j-1] + 1;
                dp[i][j] = min({replaceCost, deleteCost, insertCost});
            }
        }
    }
    
    // 返回最终的结果，即两个完整字符串的编辑距离
    return dp[len1][len2];
}

int main() {
    string str1, str2;
    cout << "请输入第一个字符串: ";
    cin >> str1;
    cout << "请输入第二个字符串: ";
    cin >> str2;
    
    int distance = levenshteinDistance(str1, str2);
    cout << "两个字符串的Levenshtein距离为: " << distance << endl;
    
    return 0;
}

代码说明与优化方向

上述代码的时间复杂度为O(n*m)，其中n和m分别是两个输入字符串的长度，空间复杂度同样为O(n*m)。如果处理非常长的字符串，可以考虑空间优化，因为dp数组每一行的计算只依赖上一行的结果，所以可以用两个一维数组交替存储，将空间复杂度降低到O(min(n,m))。

另外，如果只需要判断两个字符串的相似度是否超过某个阈值，不需要精确的距离值，还可以在dp计算过程中提前终止，当当前行的最小值已经超过阈值时，直接返回结果，进一步提升效率。

实际应用场景

这个算法可以直接用在拼写检查功能中，输入错误单词后计算它和词库中单词的Levenshtein距离，返回距离最小的几个候选词。也可以在数据清洗时用来匹配相似重复的记录，比如用户姓名、地址的模糊匹配，减少人工核对的工作量。

C++Levenshtein距离字符串相似度动态规划修改时间：2026-06-09 17:54:27