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]
示例片段：
vector<int> prev(n + 1), curr(n + 1); iota(prev.begin(), prev.end(), 0); // prev[j] = j for (int i = 1; i <h3>字符比较和索引偏移的典型错误</h3> <p>所有基于 0 的字符串访问必须严格对齐 DP 状态定义：状态 <code>dp[i][j]</code> 对应 <code>s1[0..i-1]</code> 与 <code>s2[0..j-1]</code> 的距离。常见翻车点：</p> <ul> <li>写成 <code>s1[i] == s2[j]</code>：越界且语义错，应为 <code>s1[i-1] == s2[j-1]</code> </li> <li>初始化 <code>prev</code> 时漏掉 <code>prev[0] = 0</code>，导致第一轮 <code>diag</code> 初始值错误</li> <li>交换长短串时只改了 <code>m/n</code> 计算，没同步交换 <code>s1/s2</code> 引用，结果算的是反向距离（数值虽对称，但逻辑混乱易引发后续 bug）</li> </ul> <p>滚动数组优化不是炫技——它把 10MB 内存占用降到几 KB，同时提升缓存命中率。真正容易被忽略的是 <code>diag</code> 变量的生命周期：它必须在每轮 <code>j</code> 迭代开始前从上一轮的 <code>prev[j-1]</code> 获取，并在覆盖前保存当前 <code>prev[j]</code> 值供下一轮使用。少一次临时保存，整个矩阵就错一片。</p></int>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
