滚动数组可将莱文斯坦距离空间复杂度从O(nm)降至O(min(n,m))，只需一维数组dp与临时变量topLeft，内层循环遍历较短字符串，每次用topLeft缓存左上角值，避免二维存储导致的内存超限。
为什么直接写二维DP容易内存超限
用 std::vector<:vector>></:vector> 开 n × m 的二维数组算莱文斯坦距离，当字符串长度上万时，内存占用接近 400MB（假设 int 占 4 字节），不仅慢，还可能触发 OOM。实际项目中（比如模糊匹配日志关键字、拼写纠错服务），输入长度不可控，必须降维。
怎么用滚动数组把空间压到 O(min(n, m))
状态转移只依赖上一行和当前行，因此只需保存两行：旧行 prev 和新行 curr。更进一步，可以只用一维数组 + 两个临时变量——因为每轮计算 curr[j] 时，需要的三个值是：prev[j-1]（左上）、prev[j]（正上）、curr[j-1]（正左）。用一个变量缓存上一轮的 prev[j-1] 就够了。
实操建议：
- 先确保两个字符串中较短的作为内循环变量，即让
m = std::min(s1.size(), s2.size())，避免数组过大 - 初始化一维数组
dp长度为m + 1，填满0..m（对应空串到 s2.substr(0,j) 的编辑距离） - 外层遍历长串每个字符，内层从 1 到 m 更新
dp[j]；每次迭代前用变量topLeft记住上一轮的dp[j-1]值
关键代码片段：
立即学习“C++免费学习笔记（深入）”；
int levenshtein(const std::string& s1, const std::string& s2) {
if (s1.size() < s2.size()) return levenshtein(s2, s1);
int n = s1.size(), m = s2.size();
std::vector<int> dp(m + 1);
for (int j = 0; j <= m; ++j) dp[j] = j;
<pre class='brush:php;toolbar:false;'>for (int i = 1; i <= n; ++i) {
int topLeft = dp[0], top = dp[0]++;
dp[0] = i;
for (int j = 1; j <= m; ++j) {
int newTopLeft = dp[j];
dp[j] = std::min({dp[j] + 1, dp[j-1] + 1,
topLeft + (s1[i-1] != s2[j-1])});
topLeft = newTopLeft;
}
}
return dp[m];}
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
遇到中文或 UTF-8 字符串怎么办
标准实现按字节比较，对 UTF-8 会出错——一个汉字占 3 字节，s1[i-1] != s2[j-1] 实际在比单个字节，不是字符。这不是算法问题，是输入预处理问题。
实操建议：
- 不要在原始 UTF-8 字符串上直接跑 DP；先用
std::wstring_convert（C++11/14）或第三方库（如 utf8cpp）转成std::u32string，再传入函数 - 如果确定只处理 ASCII，跳过这步；但线上服务面对用户输入，必须默认支持 Unicode
- 注意：Windows 下
std::wstring是 UTF-16，Linux/macOS 是 UCS-4，统一用char32_t更可靠
什么时候该放弃 DP 改用优化变体
当只需要判断“距离是否 ≤ k”（例如搜索相似 ID），而不是求精确值时，O(kn) 的 **Ukkonen 算法** 或 **wagner-fischer 剪枝版** 明显更快。k 通常很小（1~3），此时时间复杂度近似线性。
常见错误现象：
- 对 10 万字符文本调用完整 DP，耗时几百毫秒甚至秒级——其实只要知道“是否 ≤2”，完全可控制在 1ms 内
- 误以为所有场景都要精确距离，导致服务响应毛刺
参数差异：标准 DP 输入是两字符串，返回 int；剪枝版额外接受 int max_dist，提前终止并返回 -1 表示超限。
边界情况和编码细节容易被忽略：空字符串、全相同字符、含 \0 的 C 风格字符串混用、size() 返回 size_t 导致有符号/无符号比较警告——这些不报错，但会在特定输入下返回意外结果。
