Levenshtein距离DP必须用二维数组（或滚动两行），因dpi依赖左、上、左上三个方向值，一维数组会覆盖未使用的dpi−1；空间可优化至O(min(m,n))，需以短串为内层维度并交换输入，字符比较用s1[i−1]≠s2[j−1]避免越界。
Levenshtein距离的DP状态转移为什么必须用二维数组？
因为每个 dp[i][j] 表示的是 s1.substr(0, i) 和 s2.substr(0, j) 的最小编辑距离，它依赖左、上、左上三个方向的值——删（dp[i-1][j]）、增（dp[i][j-1]）、换（dp[i-1][j-1]）。一维数组无法同时保留上一行的完整信息，强行滚动会覆盖未使用的 dp[i-1][j-1]，导致结果错误。
常见错误现象：dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + (s1[i-1] != s2[j-1]) 中，若用一维数组且未缓存 prev_diag，dp[j-1] 在更新前已被改写，dp[i-1][j-1] 丢失。
- 正确做法：用两行滚动（
prev_row和curr_row），每次迭代前保存prev_row[j-1]为对角线值 - 初始化：
prev_row[j] = j（空串变长度j串需j次插入） - 边界处理：i=0 或 j=0 时直接取另一维度下标，无需特判
如何把空间复杂度从 O(mn) 压到 O(min(m,n))？
关键不是“选短串做列”，而是确保内层循环长度是较短字符串长度。否则滚动数组仍会分配冗余空间。实际中应先比较 s1.size() 和 s2.size()，让较短的作为第二维（即列数），再构建长度为 min_len + 1 的一维数组。
性能影响：内存访问局部性更好，缓存命中率提升；对于长串（如 10k 字符），空间从 ~100MB（10k×10k）降到 ~100KB，避免 malloc 失败或触发 GC 压力。
立即学习“C++免费学习笔记（深入）”；
- 必须交换输入：若
s1.size() > s2.size()，调用levenshtein(s2, s1)，保证内层循环次数最少 - 数组长度为
shorter.size() + 1，索引j范围是0..shorter.size() - 每次外层迭代需保留上一轮的
diag（即旧dp[j-1]），不能只靠prev变量
字符比较时为什么用 s1[i-1] != s2[j-1] 而不是 s1[i] != s2[j]？
因为 dp[i][j] 定义的是前 i 个和前 j 个字符的距离，状态索引从 1 开始，而 C++ 字符串下标从 0 开始。错写成 s1[i] 会导致越界读（当 i == s1.size() 时）或逻辑错位（首字符未参与比较）。
容易踩的坑：调试时打印 dp 表发现第一行/第一列异常，大概率是这里越界或偏移错了。
- 统一使用 1-based 状态定义，字符访问一律用
[i-1]/[j-1] - 如果硬要用 0-based 状态（
dp[i][j]对应s1[0..i]），则初始化和转移都要重推，反而易错 - VS/Clang 开启
-fsanitize=address可快速捕获此类越界
整数溢出和 early-return 优化要不要加？
要。Levenshtein 距离最大值是 max(m, n)，但中间状态不会超；真正危险的是：当两个字符串长度差极大（如 1 vs 100000），且你没做长度交换，O(mn) 时间直接爆炸。此时应加阈值剪枝。
实用建议：在函数开头加 if (abs((int)s1.size() - (int)s2.size()) > MAX_ALLOWED_DIST) return MAX_ALLOWED_DIST + 1;，比如设 MAX_ALLOWED_DIST = 100，适用于拼写纠错等场景——用户输错不可能超过百字符。
- 不推荐无条件计算全表，尤其在实时服务中
- 返回
int足够（65535 内安全），但若支持超长文本，改用size_t并检查addition overflow - GCC/Clang 可用
__builtin_add_overflow检测cost + 1是否溢出
实际编码中最容易被忽略的是：滚动数组实现中忘记在每轮内层循环开始前把 curr_row[0] 设为 i（即“删i次得到空串”），或者误把 prev_row[0] 当作常量。这两个点错一个，整个表就全偏了。
