C++如何实现Levenshtein字符串相似度算法的动态规划优化解法

Levenshtein算法也叫编辑距离算法，核心是衡量两个字符串从一个转换为另一个所需的最少编辑操作次数，编辑操作包括插入、删除、替换三种，操作次数越少说明两个字符串相似度越高。该算法在文本查重、拼写纠错、基因序列比对等场景有广泛应用。

传统动态规划解法的问题

传统的Levenshtein动态规划解法会创建一个大小为(n+1)*(m+1)的二维数组，其中n和m分别是两个字符串的长度，数组dp[i][j]表示第一个字符串前i个字符和第二个字符串前j个字符的编辑距离。这种解法的时间复杂度是O(n*m)，空间复杂度也是O(n*m)，当字符串长度较长时，会占用大量内存。

动态规划优化思路

观察二维数组的状态转移过程可以发现，dp[i][j]的计算只依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]三个状态，也就是当前行和上一行的数据。因此我们不需要存储整个二维数组，只需要保存上一行的所有状态和当前行正在计算的状态即可，这样空间复杂度可以优化到O(min(n,m))。

优化的核心步骤是：

• 选择长度较短的字符串作为列维度，减少需要保存的数组长度
• 用两个一维数组分别存储上一行和当前行的中间状态
• 每次计算完当前行后，交换两个数组的引用，继续下一行的计算

状态转移公式

编辑距离的状态转移公式如下：

如果第一个字符串的第i个字符等于第二个字符串的第j个字符，那么dp[i][j] = dp[i-1][j-1]；否则dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])，分别对应删除、插入、替换操作的最小代价。

C++源码实现

以下是优化后的Levenshtein算法C++实现代码：

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

using namespace std;

// 计算两个字符串的编辑距离，返回最小编辑操作次数
int levenshtein_distance(string str1, string str2) {
    int len1 = str1.size();
    int len2 = str2.size();
    
    // 处理边界情况，其中一个字符串为空
    if (len1 == 0) return len2;
    if (len2 == 0) return len1;
    
    // 优化空间，让列维度为较短的字符串长度
    if (len1 < len2) {
        swap(str1, str2);
        swap(len1, len2);
    }
    
    // 上一行状态数组，初始化为从空字符串到str2前j个字符的编辑距离
    vector<int> prev(len2 + 1, 0);
    for (int j = 0; j <= len2; j++) {
        prev[j] = j;
    }
    
    // 当前行状态数组
    vector<int> curr(len2 + 1, 0);
    
    for (int i = 1; i <= len1; i++) {
        // 当前行第一个元素表示str1前i个字符到空字符串的编辑距离
        curr[0] = i;
        for (int j = 1; j <= len2; j++) {
            if (str1[i-1] == str2[j-1]) {
                // 字符相同，不需要编辑操作
                curr[j] = prev[j-1];
            } else {
                // 取删除、插入、替换操作的最小值加1
                curr[j] = 1 + min(min(prev[j], curr[j-1]), prev[j-1]);
            }
        }
        // 交换数组，当前行变为下一轮的上一行
        swap(prev, curr);
    }
    
    // 最终结果为第一个字符串全部和第二个字符串全部的编辑距离
    return prev[len2];
}

int main() {
    string s1 = "kitten";
    string s2 = "sitting";
    
    int distance = levenshtein_distance(s1, s2);
    cout << "字符串 " << s1 << " 和 " << s2 << " 的编辑距离为：" << distance << endl;
    
    // 计算相似度，相似度 = 1 - 编辑距离 / 较长字符串长度
    int max_len = max(s1.size(), s2.size());
    double similarity = 1.0 - (double)distance / max_len;
    cout << "两个字符串的相似度为：" << similarity * 100 << "%" << endl;
    
    return 0;
}

代码说明

上述代码中，首先处理了边界情况，当其中一个字符串为空时，编辑距离就是另一个字符串的长度。然后通过交换字符串保证列维度是较短的字符串，减少空间占用。使用两个一维数组prev和curr分别存储上一行和当前行的状态，每次计算完当前行后交换两个数组，避免重复创建数组。最后在main函数中展示了如何调用该函数计算编辑距离和相似度。

复杂度分析

优化后的算法时间复杂度仍然是O(n*m)，因为需要遍历两个字符串的所有字符组合。空间复杂度降低到O(min(n,m))，只需要存储两个长度为较短字符串加1的数组，大幅减少了内存占用，适合处理长字符串的场景。

Levenshtein算法C++动态规划字符串相似度修改时间：2026-07-11 06:21:24