levenshtein距离通过动态规划计算，用滚动数组将空间优化至o(min(m,n))；核心是正确区分字符匹配（代价0）与替换（代价1），并严格初始化curr[0]=i防止累计错误。

要计算两个字符串之间的编辑距离（即Levenshtein距离），需通过动态规划避免重复子问题，同时将空间复杂度从O(m×n)压缩至O(min(m,n))，确保长字符串输入不触发栈溢出或内存超限。

理解Levenshtein距离的三种编辑操作

插入、删除、替换各计1步代价；空字符串到非空字符串的距离等于目标长度；两字符串首字符相同时，当前最优解直接继承左上角值，无需额外计算。

这一步不能跳过——若误将“替换”和“匹配”统一处理为+1，会导致所有相等字符也被计为一次替换，结果恒偏大。

构建滚动数组优化的状态转移表

方法一：使用两行一维数组代替二维dp表

定义 prev[0..n] 和 curr[0..n]，其中 prev[j] 表示上一行第j列值，curr[j] 表示当前行第j列值；初始化 prev[j] = j（对应空字符串到 target[0..j-1] 的插入代价）。

遍历 source 每个字符 i（从1开始索引），对每个 target 字符 j（从1开始），执行 curr[j] = min({curr[j-1] + 1, prev[j] + 1, prev[j-1] + (source[i-1] != target[j-1])})；每轮结束后 swap(prev, curr)，并重置 curr[0] = i。

【curr[0] = i 必须在每轮开头重置，否则会沿用上一轮末尾残留值，导致首列累计错误】

实现边界安全的C++模板函数

第一步：声明模板函数 template size_t levenshtein(const std::basic_string& s, const std::basic_string& t)；

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

第二步：交换输入顺序，使较短字符串为t，减少内层循环次数 → if (s.length()

第三步：申请两个 vector prev(t.length() + 1), curr(t.length() + 1)；

第四步：用 iota(prev.begin(), prev.end(), 0) 初始化 prev；进入外层 for (size_t i = 1; i

第五步：在内层循环中，curr[0] = i；然后 for (size_t j = 1; j 避免符号扩展歧义。

完整可编译源码（含测试用例）

#include #include #include #include #include

template size_t levenshtein(const std::basic_string& s, const std::basic_string prev(n + 1), curr(n + 1); std::iota(prev.begin(), prev.end(), 0); for (size_t i = 1; i (s[i - 1]) != static_cast(t[j - 1])); curr[j] = std::min({ins, del, sub}); } prev.swap(curr); } return prev[n]; }

int main() { assert(levenshtein("kitten", "sitting") == 3); assert(levenshtein("", "a") == 1); assert(levenshtein("abc", "abc") == 0); return 0; }

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！