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

在计算两个字符串的相似度时，Levenshtein距离（编辑距离）是最直观且应用广泛的指标。它表示将一个字符串变成另一个字符串所需的最少单字符编辑操作次数。使用动态规划可以系统地求解，但朴素实现会占用较多内存。下面通过C++代码展示如何使用一维数组优化空间。

一、Levenshtein距离的定义

给定字符串a和b，定义dp[i][j]为a前i个字符与b前j个字符的编辑距离。状态转移方程为：

• 若a[i-1] == b[j-1]，则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])

边界条件为dp[0][j] = j，dp[i][0] = i。

二、空间优化思路

每一行的计算只依赖上一行和当前行左侧元素，因此可用两个一维数组或单个数组配合变量滚动更新，将空间复杂度从O(mn)降为O(n)。

核心代码实现

以下为完整的C++源码，包含空间优化版本：

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

using namespace std;

// 计算Levenshtein距离，空间优化到O(min(m,n))
int levenshtein(const string& a, const string& b) {
    // 保证a是较短的字符串，节省空间
    if (a.size() > b.size()) return levenshtein(b, a);
    int m = a.size(), n = b.size();
    vector<int> dp(m + 1);
    // 初始化：a为空时，距离为0..m
    for (int i = 0; i <= m; ++i) dp[i] = i;
    
    for (int j = 1; j <= n; ++j) {
        int prev = dp[0]; // 上一行左上角
        dp[0] = j;        // 当前行第一个
        for (int i = 1; i <= m; ++i) {
            int temp = dp[i];
            if (a[i-1] == b[j-1]) {
                dp[i] = prev;
            } else {
                dp[i] = 1 + min({dp[i-1], dp[i], prev});
            }
            prev = temp;
        }
    }
    return dp[m];
}

int main() {
    string s1 = "kitten";
    string s2 = "sitting";
    cout << "Distance: " << levenshtein(s1, s2) << endl;
    return 0;
}

代码解析

上述代码中，dp数组长度仅为较短串长度加一。外层循环遍历较长串b，内层更新dp。变量prev保存左上角值，每次迭代后顺移。这样避免了二维矩阵，适合处理长文本。

三、性能与应用

优化后时间复杂度仍为O(mn)，空间降至O(min(m,n))。该算法可用于拼写检查、DNA序列比对及重复内容检测。若需处理超长字符串，可结合分块或阈值剪枝进一步优化。

四、小结

通过滚动数组技巧，C++实现Levenshtein距离既简洁又高效。理解状态转移与边界是编写正确代码的关键，读者可将示例直接嵌入项目使用。

C++Levenshtein_distance动态规划字符串相似度空间优化修改时间：2026-07-25 06:42:10