编辑距离的经典二维动态规划直观可靠却会在长字符串上占用大量内存。本文从一次批量比对内存告警出发重新标注插入、删除、替换三个来源证明当前行只依赖上一行和本行左侧并给出 Java 两行滚动实现与空串、相等串、经典样例测试。批量比较商品标题时服务处理几个很长字符串后内存突然升高。代码没有泄漏只是为长度 m 和 n 的每一对字符串都创建了(m1)*(n1)的整数表。编辑距离的时间本来就是平方级但返回值只需要右下角一个数保留整张历史表并非必要。复盘的关键是先确认每个状态依赖哪些邻居再压缩空间。告警现场表格比字符串还大定义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 两个长度 n1 的数组即可。每行开始令 curr[0]i随后从左到右填写确保 curr[j-1] 已是本轮新值。行末交换两个数组引用下一轮旧 curr 会被逐格覆盖。为了把空间降到 O(min(m,n))可让较短字符串作为列维度。三种操作从哪里转移kitten到sitting的结果为三k 替换成 se 替换成 i末尾插入 g。程序不尝试恢复具体路径只验证最小次数。空串到abc为三相同字符串为零flaw到lawn为二。四个样例覆盖初始化边界、相等字符继承和三种操作组合。若需要展示路径就不能只保留两行需额外保存方向或采用分治恢复。滚动后哪些值不能覆盖按 i、j 递增的顺序三个前驱状态都已是对应前缀的最优解。任意把前 i 个字符变成前 j 个字符的最优序列最后一步必为删除、插入、替换之一或末字符相同无需操作转移枚举了所有可能且选择最小因此由归纳法得到最优值。滚动数组只丢弃未来不再读取的行不改变任何转移输入所以与二维表结果相同。从批处理任务扩展到接口接口应对输入长度设置上限因为两行滚动只把空间降为线性时间仍是 O(mn)。批量任务可以先用长度差作为下界若只关心距离是否不超过阈值 k长度差大于 k 时直接拒绝并可使用带状 DP 减少计算。原型若还要调用外部模型判断语义相似度https://haerapi.com 可作为开发者自行评估的 API 接入选项之一但字符级距离与模型分数应分字段记录不能混成一个不可解释阈值。完整可运行代码publicclassEditDistanceRolling{staticintdistance(Stringa,Stringb){if(anull||bnull)thrownewIllegalArgumentException(null);if(a.length()b.length()){Stringta;ab;bt;}int[]prevnewint[b.length()1];int[]currnewint[b.length()1];for(intj0;jb.length();j)prev[j]j;for(inti1;ia.length();i){curr[0]i;for(intj1;jb.length();j){if(a.charAt(i-1)b.charAt(j-1))curr[j]prev[j-1];elsecurr[j]1Math.min(prev[j-1],Math.min(prev[j],curr[j-1]));}int[]tprev;prevcurr;currt;}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、码点还是规范化字符比较。总结这次内存告警不是靠换机器解决的而是靠重新阅读状态依赖当前格只需要左、上和左上。滚动数组保留了全部数学信息却不保存永远不会再访问的历史这也是动态规划空间优化最值得复用的判断方法。