Levenshtein距离不能直接用二维数组暴力填表，因为O(n×m)空间复杂度在字符串长10⁴时达100MB，易致栈溢出或内存分配失败；应改用两个一维数组滚动更新，空间优化至O(min(n,m))。
Levenshtein 距离为什么不能直接用二维数组暴力填表？
因为当字符串长度达到 10⁴ 级别时，O(n×m) 空间（比如两个 10k 字符串会申请 100M 的 int 数组）会触发栈溢出或内存分配失败。即使堆上分配，也浪费——每行计算只依赖上一行和当前行。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 改用两个一维数组：
prev和curr，长度为m+1（较短串长度 + 1），滚动更新 - 先确保
s1是较长串、s2是较短串，这样空间固定为O(min(n,m)) - 初始化
prev[j] = j（对应空串到 s2.substr(0,j) 的编辑距离） - 内层循环中，
curr[0]始终是i（s1.substr(0,i) 到空串的距离）
如何正确处理字符相等与不等的转移逻辑？
关键在状态定义：dp[i][j] 表示 s1[0..i-1] 变成 s2[0..j-1] 的最小编辑距离。转移时不是“看 s1[i] 和 s2[j]”，而是“看 s1[i-1] 和 s2[j-1]”——下标易错点。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 外层 i 从 1 到 n，内层 j 从 1 到 m
- 若
s1[i-1] == s2[j-1]，则curr[j] = prev[j-1]（无需操作） - 否则取三者最小值：
prev[j] + 1（删 s1[i-1]）、curr[j-1] + 1（插 s2[j-1]）、prev[j-1] + 1（换） - 每次内层循环结束前，交换
prev和curr指针（或用std::swap）
边界情况和性能陷阱有哪些？
常见错误现象：std::bad_alloc、结果比预期大 1、空串输入崩溃、中文 UTF-8 字符被拆成多个字节误判。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 提前检查空串：
if (s1.empty()) return s2.length();，避免进主循环 - 不要对 UTF-8 字符串直接用
operator[]比较——它比较的是字节而非字符；如需支持 Unicode，先转std::u32string或用 ICU 库 - 避免重复构造
std::vector：在函数内复用prev/curr向量，用.assign()重置 - 编译时加
-O2，滚动数组本身已让时间复杂度保持O(n×m)，但常数显著降低
C++ 优化版源码（含注释与边界防护）
#include <string>
#include <vector>
#include <algorithm>
int levenshtein(const std::string& s1, const std::string& s2) {
if (s1 == s2) return 0;
if (s1.empty()) return s2.length();
if (s2.empty()) return s1.length();
// 确保 s1 是较长串，节省空间
const std::string& a = (s1.length() >= s2.length()) ? s1 : s2;
const std::string& b = (s1.length() >= s2.length()) ? s2 : s1;
size_t n = a.length(), m = b.length();
std::vector<int> prev(m + 1), curr(m + 1);
for (size_t j = 0; j <= m; ++j) prev[j] = j;
for (size_t i = 1; i <= n; ++i) {
curr[0] = i;
for (size_t j = 1; j <= m; ++j) {
if (a[i-1] == b[j-1]) {
curr[j] = prev[j-1];
} else {
curr[j] = std::min({prev[j], curr[j-1], prev[j-1]}) + 1;
}
}
prev.swap(curr); // 滚动：prev 现在存第 i 行结果
}
return prev[m];
}
这个实现不依赖第三方库，通过长度判断 + 滚动数组 + 边界早返，覆盖了生产环境常见压力场景。真正容易被忽略的是：字符串长度差极大时（比如 1 vs 100000），仍要保证 prev 和 curr 只分配 100001 个 int，而不是 100000×100000。
