Levenshtein 编辑距离可优化至 O(min(m,n)) 空间，关键是以短串为列、用滚动数组只存两行，避免二维 vector 导致的 std::bad_alloc 和缓存不友好问题。
Levenshtein 编辑距离在 C++ 中用二维 std::vector<:vector>></:vector> 实现，字符串长度一过万就容易触发 std::bad_alloc ——这不是算法错，是空间冗余太狠。真正只需要 O(min(m, n)) 空间，关键在于只保留两行状态，且必须让短串当“列”。
为什么二维 DP 会爆内存？
标准写法声明 dp[m+1][n+1]，每个 int 占 4 字节。两个 10000 字符串，就是 10⁸ × 4 = 400MB。但计算 dp[i][j] 只依赖 dp[i-1][j]（删）、dp[i][j-1]（增）、dp[i-1][j-1]（替）——整张表根本不需要存住。
- 常见错误现象：
std::bad_alloc或程序卡死在vector构造阶段 - 性能影响：不仅内存高，还导致 CPU 缓存不友好，
dp[i][j]访问跨度大，cache miss 频繁 - 别信“先写二维再优化”的说法：线上跑着跑着 OOM，改起来比重写还疼
滚动数组必须交换输入顺序
空间从 O(mn) 压到 O(min(m,n)) 的前提是：内层循环长度取较短字符串长度。否则数组还是开太大。
- 必须先判断：
if (s1.size() > s2.size()) return levenshtein(s2, s1); - 设
m = s1.size(),n = s2.size()，则只分配长度为m + 1的一维数组（s1是短串） - 初始化
dp[j] = j，对应空串 →s1.substr(0, j)的插入代价 - 外层遍历
s2（长串），内层遍历j = 1..m；每次更新前用topLeft = dp[0]缓存左上角值 - 字符比较一律用
s1[j-1] == s2[i-1]，下标偏移不能错，否则越界或漏比首字符
std::min({a,b,c}) 在老编译器上会报错
这是 C++11 初始化列表语法，GCC 4.8、MSVC 2013 等旧环境不支持，直接编译失败。
立即学习“C++免费学习笔记（深入）”；
- 稳妥写法：
std::min(a, std::min(b, c))，无兼容性问题 - 若项目锁死 C++98，连
std::min都得手写三元：(a - 别用宏封装——模板实例化失败时错误信息极难读
- 注意：
std::min对int安全，但若泛型化到char32_t或自定义类型，得确保可用
中文和 emoji 输入时结果失真不是算法问题
std::string 是 UTF-8 字节序列。s1[i] 直接取单字节，遇到中文或 emoji 就会切开多字节码点，导致 s1[i-1] != s2[j-1] 恒为真，距离被严重高估。
- 正确做法：先转成
std::u32string，再喂给 Levenshtein 函数 - 转换示例：
std::u32string u32_s1(s1.begin(), s1.end());不行——UTF-8 不能直接迭代；得用std::wstring_convert（C++17 已弃用）或第三方库如 ICU / utf8cpp - 简单场景可跳过转换，但必须加断言：
assert(std::all_of(s1.begin(), s1.end(), [](char c) { return (c & 0x80) == 0; })); - 最容易被忽略的点：测试用例全是 ASCII，上线后用户一输“你好”，距离突然变成 4 而不是 2，排查半天才发现是编码层面崩了
