Levenshtein距离二维DP内存爆掉是因为需O(m×n)空间，而实际只需两行滚动数组优化至O(min(m,n))；通过交换prev/curr并正确初始化边界（dpi=i, dp0=j）即可。
Levenshtein距离的二维DP实现为什么内存爆了？
直接用 std::vector<:vector>></:vector> 开二维数组算 Levenshtein 距离，当字符串长度超 10⁴ 就容易 OOM 或栈溢出——因为需要 O(m×n) 空间。实际中很少真需要整个 DP 表，多数场景只关心最终距离值，或需回溯编辑路径时才保留部分行。
- 经典二维写法：
dp[i][j]表示s1.substr(0,i)到s2.substr(0,j)的最小编辑距离 - 递推式固定：
dp[i][j] = min({dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+(s1[i-1]!=s2[j-1])}) - 关键观察：计算第
i行只依赖第i-1行，因此可用两个一维数组滚动更新
怎么用两行 vector 实现空间 O(min(m,n))？
把长串放后面、短串放前面，再只维护 prev 和 curr 两行，每轮交换指针即可。注意初始化和边界处理不能错，否则 dp[0][j] 或 dp[i][0] 会全为 0 导致结果偏小。
- 先确保
s1.size() ，否则交换参数，让第一维尽量小 -
prev[j]初始为j（空串转s2.substr(0,j)需 j 次插入） -
curr[0]每轮设为i（s1.substr(0,i)转空串需 i 次删除） - 内层循环从
j=1开始，避免越界访问prev[j-1]
int levenshtein(const std::string& s1, const std::string& s2) {
if (s1.size() > s2.size()) return levenshtein(s2, s1);
int m = s1.size(), n = s2.size();
std::vector<int> prev(n + 1), curr(n + 1);
for (int j = 0; j <= n; ++j) prev[j] = j;
for (int i = 1; i <= m; ++i) {
curr[0] = i;
for (int j = 1; j <= n; ++j) {
int cost = (s1[i-1] == s2[j-1]) ? 0 : 1;
curr[j] = std::min({prev[j] + 1, curr[j-1] + 1, prev[j-1] + cost});
}
prev.swap(curr);
}
return prev[n];
}
想还原编辑操作序列？别存整张表，改用“路径压缩”
如果不仅要距离，还要知道具体做了哪些 insert/replace/delete，存二维表确实直观，但空间仍是问题。更实用的做法是：只存最后一行（prev），在计算过程中同步记录每步的决策来源（比如用 char op[i][j] 存 'D'/'I'/'R'/'M'），但这又回到 O(m×n) 空间。折中方案是分治 + 回溯：用 Hirschberg 算法，在 O(min(m,n)) 空间内还原路径，但实现复杂度高，一般业务场景用不到。
- 简单需求（如仅判断是否 ≤ 阈值）：提前终止，一旦某行所有值都 > 阈值，直接返回 false
- 调试时想看某次替换位置：在
cost==1且prev[j-1]+1 == curr[j]时记录i-1, j-1 - 注意：字符索引是
i-1和j-1，不是i、j—— 这个 off-by-one 是最常导致 debug 半天的点
为什么用 int 而不用 unsigned int？
因为 prev[j] + 1 可能溢出：当字符串很长（比如 2×10⁹ 字符），int 虽然也可能溢，但 unsigned int 溢出后变成 0，会污染后续所有计算，导致距离突变为极小值。而有符号溢出是未定义行为，但现代编译器通常按补码处理，至少不会“优雅地变 0”。
立即学习“C++免费学习笔记（深入）”；
- 生产环境建议用
size_t仅当确认长度 long long 更稳妥 - 比较操作如
curr[j] > threshold中，若threshold是int，curr[j]是unsigned，隐式转换可能引发意外（如负阈值被转成极大正数） - Clang/GCC 加
-Wsign-compare能抓到这类隐患
