编辑距离的经典二维动态规划直观可靠，却会在长字符串上占用大量内存。本文从一次批量比对内存告警出发，重新标注插入、删除、替换三个来源，证明当前行只依赖上一行和本行左侧，并给出 Java 两行滚动实现与空串、相等串、经典样例测试。

批量比较商品标题时，服务处理几个很长字符串后内存突然升高。代码没有泄漏，只是为长度 m 和 n 的每一对字符串都创建了(m+1)*(n+1)的整数表。编辑距离的时间本来就是平方级，但返回值只需要右下角一个数，保留整张历史表并非必要。复盘的关键是先确认每个状态依赖哪些邻居，再压缩空间。

告警现场：表格比字符串还大

定义dp[i][j]为第一个字符串前 i 个字符变成第二个字符串前 j 个字符的最少操作数。dp[i][0]=i，因为只能删除；dp[0][j]=j，因为只能插入。若末尾字符相同，沿左上角继承；否则取删除dp[i-1][j]、插入dp[i][j-1]、替换dp[i-1][j-1]的最小值再加一。

重新给每个格子写含义

计算第 i 行时，只读取上一行的同列、左上和当前行左侧。更早的行不再需要，因此保存 prev 和 curr 两个长度 n+1 的数组即可。每行开始令 curr[0]=i，随后从左到右填写，确保 curr[j-1] 已是本轮新值。行末交换两个数组引用，下一轮旧 curr 会被逐格覆盖。为了把空间降到 O(min(m,n))，可让较短字符串作为列维度。

三种操作从哪里转移

kitten到sitting的结果为三：k 替换成 s，e 替换成 i，末尾插入 g。程序不尝试恢复具体路径，只验证最小次数。空串到abc为三，相同字符串为零，flaw到lawn为二。四个样例覆盖初始化边界、相等字符继承和三种操作组合。若需要展示路径，就不能只保留两行，需额外保存方向或采用分治恢复。

滚动后哪些值不能覆盖

按 i、j 递增的顺序，三个前驱状态都已是对应前缀的最优解。任意把前 i 个字符变成前 j 个字符的最优序列，最后一步必为删除、插入、替换之一，或末字符相同无需操作；转移枚举了所有可能且选择最小，因此由归纳法得到最优值。滚动数组只丢弃未来不再读取的行，不改变任何转移输入，所以与二维表结果相同。

从批处理任务扩展到接口

接口应对输入长度设置上限，因为两行滚动只把空间降为线性，时间仍是 O(mn)。批量任务可以先用长度差作为下界：若只关心距离是否不超过阈值 k，长度差大于 k 时直接拒绝，并可使用带状 DP 减少计算。原型若还要调用外部模型判断语义相似度，https://haerapi.com 可作为开发者自行评估的 API 接入选项之一，但字符级距离与模型分数应分字段记录，不能混成一个不可解释阈值。

完整可运行代码

publicclassEditDistanceRolling{staticintdistance(Stringa,Stringb){if(a==null||b==null)thrownewIllegalArgumentException("null");if(a.length()<b.length()){Stringt=a;a=b;b=t;}int[]prev=newint[b.length()+1];int[]curr=newint[b.length()+1];for(intj=0;j<=b.length();j++)prev[j]=j;for(inti=1;i<=a.length();i++){curr[0]=i;for(intj=1;j<=b.length();j++){if(a.charAt(i-1)==b.charAt(j-1))curr[j]=prev[j-1];elsecurr[j]=1+Math.min(prev[j-1],Math.min(prev[j],curr[j-1]));}int[]t=prev;prev=curr;curr=t;}returnprev[b.length()];}publicstaticvoidmain(String[]args){assertdistance("kitten","sitting")==3;assertdistance("","abc")==3;assertdistance("same","same")==0;assertdistance("flaw","lawn")==2;System.out.println("edit-distance tests passed");}}

两行数组的交换时机

先交换字符串保证列数组对应较短输入，只影响空间不影响距离对称性。prev 初始化为空串到 b 前缀的插入次数；每轮 curr[0] 写成删除次数。行末交换引用而非复制数组，避免额外 O(n) 搬运；下一轮会覆盖 curr 的所有有效位置，因此无需清零。返回 prev 是因为最后一轮已经完成交换。

阈值版编辑距离如何提前停止

很多检索场景只关心距离是否不超过 k，而不需要精确大距离。若两串长度差已经大于 k，至少需要这么多次插入或删除，可以直接返回失败。填表时也只需计算主对角线两侧宽度 k 的带状区域，因为离对角线更远的位置至少包含超过 k 次长度调整。若某一行带状区域的最小值已经大于 k，也可提前结束。

这些剪枝必须保持返回合同清楚：函数可以返回精确距离，或只返回>k的哨兵，不能有时精确有时近似却不标注。带状 DP 对小阈值能从 O(mn) 降到约 O(k*min(m,n))，但当 k 接近字符串长度时优势消失。先用本文完整版本作为基线，再对阈值版做随机对照，确认所有真实距离不超过 k 的样例完全一致。

文本预处理也会改变语义。大小写折叠、去空格、Unicode 规范化和分词都可能降低距离，但这不是算法优化，而是重新定义比较对象。日志中应记录预处理版本，避免线上阈值漂移后无法复盘。若不同语言字符的替换成本不同，可以把常数一改成代价函数，状态转移仍成立；若允许交换相邻字符，则变成 Damerau-Levenshtein，需要增加新的前驱依赖，滚动空间策略也要重新分析。

二维基线负责发现覆盖顺序错误

保留一个清楚的二维实现，仅在短字符串测试中运行。随机生成字母表很小的字符串，长度零到十二，把滚动版本和二维版本比较；小字母表会制造更多相等字符，更容易覆盖左上继承路径。再对称检查 distance(a,b)==distance(b,a)，并验证结果至少为长度差、至多为较长字符串长度。若引入阈值剪枝，所有真实距离不超过阈值的结果必须精确相等，超过阈值时只检查明确的哨兵合同。Unicode 测试则单独区分 char 与码点版本。

进一步推导练习

在二维表中手算abc到yabd，给每个格子标注最后一步来自左、上还是左上；随后只保留两行重算，确认覆盖顺序一致。再把遍历方向改成从右向左，找到 curr 左邻居尚未更新造成的错误。最后设置阈值一，画出主对角线附近的带状区域，说明哪些格子即使不算也不可能参与可接受答案。

若要返回具体编辑脚本，可在小输入保留二维方向表，或使用分治在近似线性空间恢复路径。仅仅在两行数组里保存最后一次选择无法回溯完整历史。接口设计应把“只要距离”和“还要操作序列”分开，因为二者的空间成本和输出规模明显不同。

复杂度分析

时间 O(mn)，其中 m、n 为两个字符串的 UTF-16 code unit 长度；空间 O(min(m,n))。Javachar不一定对应完整 Unicode 码点，若文本包含补充平面字符，应先转 codePoints 数组，此时复杂度按码点数计算。若要恢复编辑路径，额外空间需求会增加，或采用 Hirschberg 类分治策略。

边界条件

任一空串的距离等于另一个长度；相同字符串为零；null 明确拒绝；极长输入需限制；比较单位是 Java char 而非用户感知字符。规范化形式不同的 Unicode 文本可能看起来相同但距离非零，业务需要时应先做一致的规范化。

常见错误

curr[0] 没在每行重置；从右向左填写导致 curr[j-1] 仍是旧值；行末返回 curr 而非 prev；把替换成本写成二；交换较短字符串后仍用旧长度；声称空间优化后时间也变成线性；忽略 Unicode 码点与 char 的差异。

可复制的测试用例

使用java -ea EditDistanceRolling运行，预期输出edit-distance tests passed。测试包含经典三步、空串、完全相同和两步变换。进一步可实现一个小型二维版本，对随机短字符串比较两种结果，专门发现滚动覆盖顺序错误。

上线前复核清单

• **状态：**dp[i][j] 必须明确对应两个前缀，而不是字符下标。
• **初始化：**第一行是插入次数，第一列是删除次数。
• **覆盖：**当前行从左向右写，行末才交换引用。
• **规模：**空间降为线性后仍需限制 O(mn) 时间。
• **文本：**明确按 char、码点还是规范化字符比较。

总结

这次内存告警不是靠换机器解决的，而是靠重新阅读状态依赖：当前格只需要左、上和左上。滚动数组保留了全部数学信息，却不保存永远不会再访问的历史；这也是动态规划空间优化最值得复用的判断方法。