Levenshtein距离通过动态规划计算，用滚动数组将空间优化至O(min(m,n))；核心是正确区分字符匹配（代价0）与替换（代价1），并严格初始化curr[0]=i防止累计错误。
要计算两个字符串之间的编辑距离（即Levenshtein距离），需通过动态规划避免重复子问题，同时将空间复杂度从O(m×n)压缩至O(min(m,n))，确保长字符串输入不触发栈溢出或内存超限。
理解Levenshtein距离的三种编辑操作
插入、删除、替换各计1步代价；空字符串到非空字符串的距离等于目标长度；两字符串首字符相同时，当前最优解直接继承左上角值，无需额外计算。
这一步不能跳过——若误将“替换”和“匹配”统一处理为+1，会导致所有相等字符也被计为一次替换，结果恒偏大。
构建滚动数组优化的状态转移表
方法一：使用两行一维数组代替二维dp表
立即学习“C++免费学习笔记（深入）”；
定义 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
第二步：交换输入顺序，使较短字符串为t，减少内层循环次数 → if (s.length()
第三步：申请两个 vector
第四步：用 iota(prev.begin(), prev.end(), 0) 初始化 prev；进入外层 for (size_t i = 1; i
第五步：在内层循环中，curr[0] = i；然后 for (size_t j = 1; j 避免符号扩展歧义。
完整可编译源码（含测试用例）
#include <string> #include <vector> #include <algorithm> #include <iota> #include <cassert>
template<typename CharT> size_t levenshtein(const std::basic_string<CharT>& s, const std::basic_string<CharT>& t) { if (s.length() < t.length()) return levenshtein(t, s); const size_t n = t.length(); std::vector<size_t> prev(n + 1), curr(n + 1); std::iota(prev.begin(), prev.end(), 0); for (size_t i = 1; i <= s.length(); ++i) { curr[0] = i; for (size_t j = 1; j <= n; ++j) { const size_t ins = curr[j - 1] + 1; const size_t del = prev[j] + 1; const size_t sub = prev[j - 1] + (static_cast<unsigned char>(s[i - 1]) != static_cast<unsigned char>(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; }
