如何用C++实现Levenshtein距离动态规划算法的存储优化解法

Levenshtein距离又称编辑距离，指两个字符串之间，由一个转换成另一个所需的最少编辑操作次数，操作包括插入、删除、替换字符。传统动态规划解法需要维护一个大小为(m+1)*(n+1)的二维数组，其中m和n分别是两个字符串的长度，空间复杂度为O(mn)。实际上状态转移时，当前位置的状态只依赖上一行同列、上一行前一列、当前行前一列三个状态，因此可以压缩存储维度，将空间复杂度降到O(min(m,n))。

算法核心逻辑

假设我们有两个字符串s1和s2，长度分别为len1和len2，我们定义dp[i][j]表示s1的前i个字符和s2的前j个字符的Levenshtein距离。状态转移方程为：

• 如果s1[i-1] == s2[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])，分别对应删除、插入、替换操作

优化时我们取长度较小的字符串作为列维度，使用一维数组存储当前行的状态，再用一个变量保存左上角的状态值，即可完成所有状态转移。

完整C++实现代码

以下是存储优化后的Levenshtein距离计算实现，包含边界处理和完整的逻辑：

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

using namespace std;

// 计算两个字符串的Levenshtein距离，存储优化版本
int levenshteinDistanceOptimized(const string& s1, const string& s2) {
    int len1 = s1.size();
    int len2 = s2.size();
    
    // 保证len1是较短的字符串长度，减少空间占用
    if (len1 > len2) {
        return levenshteinDistanceOptimized(s2, s1);
    }
    
    // 边界情况：如果其中一个字符串为空，距离就是另一个字符串的长度
    if (len1 == 0) {
        return len2;
    }
    if (len2 == 0) {
        return len1;
    }
    
    // 初始化一维dp数组，大小为len1 + 1，对应上一行的状态
    vector<int> dp(len1 + 1);
    // 初始化第一行，dp[j]表示s1前0个字符和s2前j个字符的距离，即j次插入
    for (int j = 0; j <= len1; ++j) {
        dp[j] = j;
    }
    
    // 遍历s2的每个字符
    for (int i = 1; i <= len2; ++i) {
        // 当前行的第一个元素，对应s1前0个字符和s2前i个字符的距离，即i次删除
        int prev = dp[0];
        dp[0] = i;
        // 遍历s1的每个字符
        for (int j = 1; j <= len1; ++j) {
            int temp = dp[j]; // 保存当前dp[j]，作为下一轮的prev（左上角值）
            if (s2[i-1] == s1[j-1]) {
                // 字符相同，直接取左上角的值
                dp[j] = prev;
            } else {
                // 字符不同，取左、上、左上三个位置的最小值加1
                dp[j] = 1 + min(min(dp[j-1], dp[j]), prev);
            }
            prev = temp; // 更新prev为下一轮的左上角值
        }
    }
    
    return dp[len1];
}

int main() {
    string str1 = "kitten";
    string str2 = "sitting";
    int distance = levenshteinDistanceOptimized(str1, str2);
    cout << "字符串"" << str1 << ""和"" << str2 << ""的Levenshtein距离为：" << distance << endl;
    
    str1 = "hello";
    str2 = "world";
    distance = levenshteinDistanceOptimized(str1, str2);
    cout << "字符串"" << str1 << ""和"" << str2 << ""的Levenshtein距离为：" << distance << endl;
    
    return 0;
}

复杂度分析

优化后的算法时间复杂度仍然是O(len1 * len2)，因为需要遍历两个字符串的所有字符组合。空间复杂度降为O(min(len1, len2))，只需要一个长度为较短字符串长度加一的一维数组，相比传统二维数组的实现大幅减少了空间占用，在字符串长度较长时优势更加明显。

注意事项

• 实现时先判断两个字符串的长度，始终让较短的字符串作为一维数组的长度，进一步降低空间消耗
• 状态转移过程中要正确保存左上角的状态值，避免被覆盖导致计算错误
• 边界情况要处理到位，当其中一个字符串为空时，距离就是另一个字符串的长度

Levenshtein_distanceC++动态规划字符串相似度修改时间：2026-07-04 18:57:31