Levenshtein距离不能直接用二维数组暴力填表，因为O(n×m)空间复杂度在字符串长10⁴时达100MB，易致栈溢出或内存分配失败；应改用两个一维数组滚动更新，空间优化至O(min(n,m))。
Levenshtein 距离为什么不能直接用二维数组暴力填表？
因为当字符串长度达到 10⁴ 级别时，O(n×m) 空间（比如两个 10k 字符串会申请 100M 的 int 数组）会触发栈溢出或内存分配失败。即使堆上分配，也浪费——每行计算只依赖上一行和当前行。
实操建议：
- 改用两个一维数组：
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]”——下标易错点。
实操建议：
- 外层 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 字符被拆成多个字节误判。
实操建议：
- 提前检查空串：
if (s1.empty()) return s2.length();，避免进主循环 - 不要对 UTF-8 字符串直接用
operator[]比较——它比较的是字节而非字符；如需支持 Unicode，先转std::u32string或用 ICU 库 - 避免重复构造
std::vector：在函数内复用prev/curr向量，用.assign()重置 - 编译时加
-O2，滚动数组本身已让时间复杂度保持O(n×m)，但常数显著降低
C++ 优化版源码（含注释与边界防护）
prev
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
