Levenshtein距离滚动数组优化空间复杂度为O(min(m,n))，需用两行数组并维护diag变量保存左上角值，不可用一维数组硬推；短串应作列方向，字符比较须用s1[i-1]和s2[j-1]，初始化与索引偏移须严格对齐状态定义。
Levenshtein 距离的朴素二维 DP 实现空间复杂度是 O(m*n)，但实际只需要两行——滚动数组优化后可压到 O(min(m, n))，且不影响正确性和可读性。
为什么必须用滚动数组而不是完整二维表
当字符串长度超过几千时，vector<vector>>(m+1, vector<int>(n+1))</int></vector> 会触发大量堆内存分配，不仅慢，还可能因栈溢出或内存不足失败；而两行数组复用，缓存局部性更好，现代 CPU 预取更有效。
- 输入字符串长度差很大时（如
s1长 10、s2长 10000），应让短串做列方向，即交换参数顺序，使空间为O(min(m,n)) - 不能只用一维数组硬推（常见错误）：
dp[j]在更新时依赖上一行的dp[j-1]和当前行的dp[j]，不保存“左上角”值会导致覆盖丢失 - 必须额外缓存一个变量记录“左上角”（即未被覆盖前的
dp[j-1]上轮值）
levenshtein_distance 函数的边界与初始化细节
第一行 dp[0][j] = j 表示空串变 s2.substr(0,j) 需 j 次插入；第一列 dp[i][0] = i 同理。滚动实现中，这转化为：
- 初始化
prev数组为{0,1,2,...,n} - 每次迭代开始时，
curr[0] = i（即第i行首列） - 内层循环从
j = 1开始，避免越界且跳过已设的curr[0]
示例片段：
立即学习“C++免费学习笔记（深入）”；
vector<int> prev(n + 1), curr(n + 1);
iota(prev.begin(), prev.end(), 0); // prev[j] = j
for (int i = 1; i <= m; ++i) {
curr[0] = i;
int diag = prev[0]; // “左上角”初始值：prev[0] 即 dp[i-1][0]
for (int j = 1; j <= n; ++j) {
int temp = prev[j]; // 先存下，后面要当新的 diag
if (s1[i-1] == s2[j-1]) {
curr[j] = diag;
} else {
curr[j] = 1 + min({prev[j], curr[j-1], diag});
}
diag = temp;
prev[j] = curr[j]; // 可选：若需复用 prev，此处赋值
}
prev.swap(curr); // 交换指针，避免拷贝
}
字符比较和索引偏移的典型错误
所有基于 0 的字符串访问必须严格对齐 DP 状态定义：状态 dp[i][j] 对应 s1[0..i-1] 与 s2[0..j-1] 的距离。常见翻车点：
- 写成
s1[i] == s2[j]：越界且语义错，应为s1[i-1] == s2[j-1] - 初始化
prev时漏掉prev[0] = 0，导致第一轮diag初始值错误 - 交换长短串时只改了
m/n计算，没同步交换s1/s2引用，结果算的是反向距离（数值虽对称，但逻辑混乱易引发后续 bug）
滚动数组优化不是炫技——它把 10MB 内存占用降到几 KB，同时提升缓存命中率。真正容易被忽略的是 diag 变量的生命周期：它必须在每轮 j 迭代开始前从上一轮的 prev[j-1] 获取，并在覆盖前保存当前 prev[j] 值供下一轮使用。少一次临时保存，整个矩阵就错一片。
