Levenshtein二维DP空间爆炸因需O(m×n)内存，如字符串长10⁴时达100MB，触发bad_alloc；实际仅依赖上一行和左邻值，可用两行滚动数组优化至O(min(m,n))。
Levenshtein 距离的二维 DP 实现为什么空间爆炸？
直接套用教科书式二维 DP，dp[i][j] 表示 s1[0..i-1] 到 s2[0..j-1] 的编辑距离，时间 O(mn)，空间也是 O(mn)。当字符串长度上万时，dp 数组可能占用数百 MB 内存，且缓存不友好——这不是理论问题，是真实跑 std::bad_alloc 的原因。
关键在：计算 dp[i][j] 只依赖上一行 dp[i-1][*] 和当前行已算出的 dp[i][j-1]、dp[i-1][j-1]。整张表根本不需要存住。
- 只保留两行：用
prev_row和curr_row交替滚动 - 进一步压缩到单行：只需保存上一行的前一个值（即
dp[i-1][j-1]），其余用变量暂存 - 注意边界：
i==0或j==0时距离就是长度差，别漏初始化
如何用一维数组 + 两个变量完成 Levenshtein 计算？
核心是复用 dp[j] 数组，并在每次内层循环中维护三个关键状态：diag（即旧的 dp[j-1]，对应 dp[i-1][j-1]）、left（刚算出的 dp[j]，即 dp[i][j-1]）、top（上轮的 dp[j]，即 dp[i-1][j]）。每轮更新后，diag 要及时设为上轮的 top。
示例片段（C++）：
立即学习“C++免费学习笔记（深入）”；
int levenshtein(const std::string& s1, const std::string& s2) {
int m = s1.size(), n = s2.size();
std::vector<int> dp(n + 1);
for (int j = 0; j <= n; ++j) dp[j] = j;
int diag = 0;
for (int i = 1; i <= m; ++i) {
int top = dp[0];
dp[0] = i;
for (int j = 1; j <= n; ++j) {
int left = dp[j];
int new_diag = diag;
diag = dp[j]; // 保存为下轮的 top
dp[j] = s1[i-1] == s2[j-1] ? new_diag : std::min({dp[j-1], dp[j], new_diag}) + 1;
}
}
return dp[n];
}
为什么 std::min({a,b,c}) 在某些编译器下会报错？
这是 C++11 初始化列表语法，但部分老版本 GCC（如 4.8）或 MSVC 早期版本不完全支持。更稳妥写法是嵌套调用 std::min(a, std::min(b, c))，或者用三元运算符手写最小值逻辑。
- 若项目需兼容 C++98，必须避免花括号初始化列表
-
std::min对非 POD 类型可能引发模板实例化失败，纯整数场景无风险 - 性能上无差别，现代编译器都会内联优化
Levenshtein 算法的实际使用陷阱
很多人直接拿它做“模糊匹配”，却忽略了几个硬伤：
- 对长字符串开销仍高：O(mn) 时间不可忽视，10k × 10k 字符串要百亿次比较
- 不区分语义：把 "abc" → "xyz" 和 "the" → "and" 都算作距离 3，但后者更“合理”
- 未归一化：返回的是绝对编辑步数，跨长度比较需除以
max(len1, len2)或len1+len2 - 中文处理需先 UTF-8 解码为 Unicode 码点，否则一个汉字被拆成 3 字节导致距离失真
真正上线前，务必确认输入长度是否可控，以及是否真的需要精确编辑距离——有时候 std::string::find 或 Suffix Array 更快，也足够用。
