LeetCode热题100刷到第72题编辑距离时我停了一下。这道题不像两数之和那样看完题就有思路也不像二叉树遍历那样有个固定的递归框架可以套。它是很多人动态规划从“背模板”到“真正理解”的分水岭。我当年用Java刷这道题第一遍照着题解敲完感觉懂了过了两周二刷又把索引偏移写错二维DP直接数组越界。后来在面试里问过不少候选人这道题发现能默写代码的人不少但能讲清楚“为什么状态转移方程长这样”“为什么一维优化时需要保存左上角变量”的人远比我预想的少。这篇文章想解决的就是编辑距离从“看懂题解”到“独立做出”之间那段距离。我会从状态定义、转移方程推导、Java实现的三种形态、空间优化里的差一错误一路讲到拼写纠错、序列比对等实际应用场景。无论你是准备Java后端面试、刷力扣热题100还是在项目里需要算文本相似度这篇文章都能给你一套可以直接上手的思路顺便帮你避掉几个我踩过的坑。1. 编辑距离为什么能进热题100这道题真正考察的东西编辑距离的问题描述很短给你两个单词 word1 和 word2你可以对 word1 执行插入一个字符、删除一个字符、替换一个字符这三种操作返回把 word1 变成 word2 所需的最少操作次数。题目本身没有绕弯子LeetCode上函数签名也很简单输入是两个字符串输出是一个整数。但就是这么一道短题在热题100里占了一个很稳定的位置原因在于它既考了动态规划的基础模型又考了代码落地的细节。1.1 面试官想透过这道题看到什么我在技术面试中问这道题重点从来不是候选人能不能在三分钟内写出正确答案。我会先让候选人讲讲思路然后追问三个问题状态是怎么定义的为什么转移方程是那个样子能不能把空间复杂度优化到O(n)这三个问题对应三个层次的考察点。第一层是建模能力。能不能把“字符串编辑”这种看起来需要模拟所有操作序列的问题抽象成二维动态规划。不会建模的人很容易一上来就想着暴力搜索或者试图用双指针贪心但编辑距离里插入和删除会改变字符的对应关系双指针根本没法处理。第二层是状态转移的逻辑。dp[i][j]为什么能由三个子状态推出这需要候选人讲清楚“最后一次操作”的思考方式。第三层是工程细节。一维DP优化时左上角的值怎么保住Java实现里charAt的索引为什么是i-1和j-1这些细节能筛掉大量“背题解”的候选人。所以这道题真正考的不是记忆力而是你有没有把动态规划当成一种思维方式来内化。热题100里很多题都有类似特点但编辑距离是其中把“模型理解”和“细节实现”结合得最紧密的一道。1.2 为什么直接模拟操作序列不可行先看一个朴素思路既然只有插入、删除、替换三种操作那我能不能用递归枚举所有可能的操作序列理论上可以但两个字符串长度最长为500操作序列长度可能到1000每一步三种选择总复杂度是O(3^(mn))。这个数字大到任何机器都算不完。问题出在没有复用。假设word1的前3个字符变成word2的前5个字符这个子问题会被无数条不同的操作路径反复遇到。比如你先删一个字符再从word1[0..2]变到word2[0..4]和你先替换一个字符再把剩下部分变过去最后都会落到同一个子问题上。动态规划的本质就是把这种重复计算缓存下来用一张表记录每次计算的结果。这也是为什么编辑距离是动态规划经典题——它的最优子结构和重叠子问题都太典型了。那重叠的子问题长什么样我们把问题定义为“word1的前i个字符变成word2的前j个字符需要多少次操作”记为dp[i][j]。任何一个更长字符串的问题都可以通过缩短i或j来缩小最后都会拆到一系列基础状态上。只要把每个dp[i][j]算一次复杂度就变成O(mn)这也就是热题100里编辑距离的常态解法。2. 状态定义与转移方程的推导从“最后一次操作”出发状态定义是动态规划的命门。编辑距离的状态很好记dp[i][j]表示word1的前i个字符转换成word2的前j个字符所需的最小操作次数。注意这里说的是“前i个字符”不是“第i个字符”这个前缀的视角非常重要它保证了子问题之间可以自然衔接。2.1 三个方向分别对应哪三种操作推导转移方程时我最喜欢用“最后一次操作”这个角度。假设我们已经知道所有规模更小的子问题的答案现在要算dp[i][j]也就是从word1[0..i-1]变到word2[0..j-1]的最小代价。既然最后一步操作一定是三种操作之一我们分别看第一种最后一步是删除。也就是说在完成删除之前word1的前i-1个字符已经成功变成了word2的前j个字符此时word1的第i个字符是多余的删掉它就好。那么dp[i][j] dp[i-1][j] 1。第二种最后一步是插入。在完成插入之前word1的前i个字符已经变成了word2的前j-1个字符然后往末尾插入word2的第j个字符就完成了整个转换。所以dp[i][j] dp[i][j-1] 1。第三种最后一步是替换。在替换之前word1的前i-1个字符已经变成了word2的前j-1个字符然后把word1的第i个字符替换成word2的第j个字符。如果这两个字符本来就相等替换成本是0不需要额外操作如果不相等成本是1。所以dp[i][j] dp[i-1][j-1] cost其中cost是0或1。因为我们要求的是最小操作次数所以在这三种可能里取最小值。于是一行代码就出来了dp[i][j] Math.min( dp[i - 1][j] 1, // 删除 Math.min( dp[i][j - 1] 1, // 插入 dp[i - 1][j - 1] cost // 替换或不变 ) );很多人会问为什么只考虑最后一步因为插入、删除、替换这三种操作本身是有对称性的。最后一步是删除对应前面的目标是dp[i-1][j]最后一步是插入对应dp[i][j-1]最后一步是替换对应dp[i-1][j-1]。三个方向正好把状态矩阵里的“上方”“左方”“左上角”全部覆盖到了。你不需要考虑更早的操作因为更早的操作已经包含在子问题的最优解里了。2.2 边界条件为什么是 i 和 j边界条件是动态规划最容易写错的部分但编辑距离的边界特别直观只要你理解了它的含义。当i等于0时word1是空字符串要变成word2的前j个字符只能不断插入j个字符所以dp[0][j] j。当j等于0时word2是空字符串要把word1的前i个字符变成空串只能不断删除i个字符所以dp[i][0] i。在代码里就是两个循环for (int i 0; i m; i) dp[i][0] i; for (int j 0; j n; j) dp[0][j] j;这里也是经典的“差一错误”高发地。有些人会把dp[0][j]写成0有些人会漏掉dp[i][0]的初始化导致后面从i1开始循环时第一列全是0最终答案错误。我的经验是每次写完DP都先用一个小例子在纸上推一遍比如word1horse、word2ros手动把dp表前两行填出来马上就能发现对不对。3. Java实现的三级跳暴力递归、记忆化搜索、迭代DP很多刷题文章直接给最终解法但我觉得编辑距离这类题最适合从暴力递归开始走一遍。原因很简单递归版本和状态转移方程长得一模一样它帮助你验证思路是否正确确认思路没问题后再一步步加上缓存、改成迭代整个理解就立住了。3.1 暴力递归先验证思路再追求效率先写一个直接对应转移方程的递归函数。函数参数分别是word1、word2、当前要处理的索引i、j返回的是dp[i][j]的值。public int minDistance(String word1, String word2) { int m word1.length(), n word2.length(); return dfs(word1, word2, m, n); } private int dfs(String word1, String word2, int i, int j) { // 空串边界 if (i 0) return j; if (j 0) return i; int cost word1.charAt(i - 1) word2.charAt(j - 1) ? 0 : 1; int delete dfs(word1, word2, i - 1, j) 1; int insert dfs(word1, word2, i, j - 1) 1; int replace dfs(word1, word2, i - 1, j - 1) cost; return Math.min(delete, Math.min(insert, replace)); }这个版本在LeetCode上会超时因为没有任何复用重复子问题被算了太多次。但它有一个不可替代的价值思路清晰到一眼就能和转移方程对应起来。如果你对状态定义还有模糊先写这个版本自查比直接硬记代码有效得多。3.2 记忆化搜索在递归树上加缓存暴力递归慢是因为同一个(i,j)会被不同的递归路径反复计算。那就在递归函数外放一个二维数组memo每次算完把结果存进去下次进来时先查缓存。int[][] memo; public int minDistance(String word1, String word2) { int m word1.length(), n word2.length(); memo new int[m 1][n 1]; for (int[] row : memo) { Arrays.fill(row, -1); } return dfs(word1, word2, m, n); } private int dfs(String word1, String word2, int i, int j) { if (i 0) return j; if (j 0) return i; if (memo[i][j] ! -1) return memo[i][j]; int cost word1.charAt(i - 1) word2.charAt(j - 1) ? 0 : 1; int delete dfs(word1, word2, i - 1, j) 1; int insert dfs(word1, word2, i, j - 1) 1; int replace dfs(word1, word2, i - 1, j - 1) cost; memo[i][j] Math.min(delete, Math.min(insert, replace)); return memo[i][j]; }这里有一个Java细节二维memo数组初始化时用Arrays.fill(row, -1)逐个填充为-1因为编辑距离的结果不可能是负数用-1表示“还没算过”是安全的。记忆化搜索的时间复杂度已经是O(mn)空间复杂度也是O(mn)和迭代DP一致。有些人面试时会纠结到底写记忆化还是写迭代我的建议是如果你对递归更自信写记忆化完全没问题面试官能看懂如果你想展示对动态规划的理解更深入写迭代DP更好因为它离“空间优化”只有一步之遥。3.3 迭代DP面试中最高效的答卷迭代DP用两层循环按顺序填表。外层遍历i内层遍历j每一格都从它的上方、左方、左上角三个格子推导出来。public int minDistance(String word1, String word2) { int m word1.length(), n word2.length(); int[][] dp new int[m 1][n 1]; for (int i 0; i m; i) dp[i][0] i; for (int j 0; j n; j) dp[0][j] j; for (int i 1; i m; i) { for (int j 1; j n; j) { int cost word1.charAt(i - 1) word2.charAt(j - 1) ? 0 : 1; dp[i][j] Math.min( dp[i - 1][j] 1, Math.min(dp[i][j - 1] 1, dp[i - 1][j - 1] cost) ); } } return dp[m][n]; }时间复杂度O(mn)空间复杂度O(mn)。LeetCode原题约束m和n都不超过500这个版本直接提交是能过的。代码结构也很规整最难的地方就是记住charAt的下标要减去1因为dp的行列索引是从1开始计数的而字符串的字符索引从0开始。如果你想在性能上再抠一点可以把word1和word2先转成char数组char[] s1 word1.toCharArray()后面循环里用s1[i-1]取值。这样避免了多次调用charAt在字符串较长时稍微快一点。不过这属于锦上添花对解题不是必要的。4. 空间优化实战从二维数组到一维数组的差一错误编辑距离的常规解法空间是O(mn)。面试官几乎一定会追问能不能把空间优化到O(n)。答案是可以而且有两种做法滚动数组和一维DP。这两种做法原理一样但一维DP的代码陷阱很多值得单独拆开讲。4.1 滚动数组为什么两行就够观察转移方程可以发现dp[i][j]只依赖当前行的左边dp[i][j-1]、上一行的同列dp[i-1][j]、上一行的左边dp[i-1][j-1]。换句话说计算第i行的时候只需要第i-1行的数据更早的行永远用不到了。所以不需要开一个m1乘n1的矩阵只要两个长度为n1的数组prev保存上一行cur保存当前行。public int minDistance(String word1, String word2) { int m word1.length(), n word2.length(); int[] prev new int[n 1]; int[] cur new int[n 1]; for (int j 0; j n; j) prev[j] j; for (int i 1; i m; i) { cur[0] i; for (int j 1; j n; j) { int cost word1.charAt(i - 1) word2.charAt(j - 1) ? 0 : 1; cur[j] Math.min( prev[j] 1, Math.min(cur[j - 1] 1, prev[j - 1] cost) ); } int[] tmp prev; prev cur; cur tmp; } return prev[n]; }这里最需要注意的是每一行开始前要给cur[0]赋值也就是当前行第一列的值。很多人在这个细节上翻车因为prev[0]一直没变如果忘记更新cur[0]第一列就会沿用上一行的旧值导致整行都不对。滚动数组比二维DP多了一个“行切换”的动作理解清楚prev和cur的职责写起来就不容易乱。4.2 一维DP如何用prev变量守住左上角更极致的优化是只用一个数组。此时dp[j]保存的是“当前行第j列的最新值”但在更新之前dp[j]里存的还是上一行第j列的值。因此更新逻辑变成dp[j]是上方dp[j-1]是左方还需要一个变量保存左上角的值。看代码之前请记住一个关键点每一轮内层循环开始时我们要用一个变量prev记录dp[j]的旧值这个旧值其实是上一行第j列的值。而在进入下一个j之前prev会更新成当前这个旧值这样下一轮循环时prev恰好就是左上角的值。我直接用代码给出实现然后解释为什么这么写。public int minDistance(String word1, String word2) { int m word1.length(), n word2.length(); int[] dp new int[n 1]; for (int j 0; j n; j) dp[j] j; for (int i 1; i m; i) { int prev dp[0]; // 上一行的左上角初始为dp[i-1][0] dp[0] i; // 当前行第一列 for (int j 1; j n; j) { int temp dp[j]; // 保存更新前的旧值即上一行第j列 int cost word1.charAt(i - 1) word2.charAt(j - 1) ? 0 : 1; dp[j] Math.min( dp[j] 1, // 上方旧值还是dp[i-1][j] Math.min(dp[j - 1] 1, prev cost) // 左方与左上角 ); prev temp; // 下一轮j1时temp正好是左上角 } } return dp[n]; }我再用一个表格说明每轮内层循环里关键变量在更新前后的含义变量更新前含义更新后含义dp[j]dp[i-1][j]上一行同列dp[i][j]当前行当前列dp[j-1]dp[i][j-1]本行已更新的左方不变prevdp[i-1][j-1]左上角变成temp即dp[i-1][j]供下一轮使用这里有个很容易犯的错有人习惯先把dp[j]更新完再取左上角的值结果发现左上角已经被覆盖了。正确顺序必须是“先暂存temp - 计算新dp[j] - 再把temp赋给prev”不能反过来。4.3 空间优化的收益与适用边界一维DP的空间复杂度是O(n)其中n取word2的长度。如果word1比word2长很多可以先交换两个字符串让n尽量小这样数组更短。比如word1长度5000、word2长度10如果你不交换数组开11就够了如果按默认的n5000数组就要开5001。所以有些人会在方法开头加一行if (word1.length() word2.length()) { String tmp word1; word1 word2; word2 tmp; }这个交换不影响结果因为编辑距离本身是对称的从A变到B和从B变到A的操作次数相同。但交换后n变小了循环里的内层循环次数变少空间也省了。这个小技巧在LeetCode的Java提交里能明显提升排名工作中也适合处理长度差异很大的文本对。5. 编辑距离的落地场景拼写纠错、序列比对与自定义代价很多人刷算法题时会有个疑问这种题除了面试还有什么用编辑距离是我能举出最多实际案例的算法之一它在搜索引擎、输入法、生物信息学、数据库系统里都有广泛应用。5.1 拼写纠错里的编辑距离工程化最常见的场景是拼写纠错。用户输入helo搜索引擎或输入法需要判断出用户可能想打hello。这里的helo到hello编辑距离是1在候选词典里属于距离最小的词之一系统就会把它作为纠错建议。再比如recieve和receive编辑距离是1互调两个字符这种错误标准的Levenshtein距离会把它们算成2一次删除加一次插入所以有些系统会使用扩展的Damerau-Levenshtein距离把相邻字符交换也作为一种独立操作代价为1。但实际产品里不会对几十万词的词典逐个做编辑距离计算那太慢了。工程上的做法通常分两步先用倒排索引、n-gram或BK树缩小候选范围把可能相关的词筛到几十个再用编辑距离作为精排指标排序后返回Top N。编辑距离在这里不是独立的系统而是整个纠错管道靠近末端的一个评分模块。我在做搜索联想功能时就是这么组合使用的。5.2 基因序列与文本相似度生物信息学里DNA序列可以被看作只有A、C、G、T四种字符的字符串。比较两段序列的相似度时插入、缺失、替换分别对应生物学上的插入突变、删除突变和点突变。基础的编辑距离可以直接用但科研场景通常会用更复杂的打分机制比如替换不同字符的代价不一样连续gap的惩罚和单次gap也不一样。这些都是在标准编辑距离模型上做加权扩展。文本相似度方面编辑距离可以用于查重、客服工单聚合、论文相似度粗筛。两个文本之间的编辑距离越小说明它们越相似。我之前做过一个简历解析项目需要判断用户上传的简历和系统中已有简历是不是同一个人的版本当时的做法就是把两份文本先做规范化再去掉停用词后计算编辑距离设定一个阈值低于阈值就判定为相似文档。效果比单纯用哈希去重好很多因为能容忍细微的文字差异。但这种用法有一个边界需要清楚编辑距离对长文本非常不友好两个一万字的文档直接做DP时间和内存都可能爆炸。所以实际工程里很少对全文算编辑距离通常会先分句、分段落或者用simhash之类的算法做初筛然后再对候选片段做精细的编辑距离计算。5.3 自定义操作代价与路径回溯标准编辑距离把三种操作都看成代价1但真实业务里不一定公平。OCR识别后处理中某些字符之间混淆概率高比如0和O、l和1替换它们的代价应该比替换a和z低。搜索场景中删除一个空格和替换一个核心关键词代价权重也不一样。实现时只需要把转移方程里对应的1改成不同权重即可状态定义和整体框架完全不用动。如果应用不仅要“最小距离是多少”还想知道“具体怎么变换的”就需要做路径回溯。做法是在填表的同时记录每个格子是从哪个方向转移来的最后从dp[m][n]倒着走回dp[0][0]把每一步操作还原出来。回溯的规则是如果当前格子来自上方说明做了一次删除操作来自左方说明做了一次插入来自左上角且字符相等说明没有操作来自左上角且字符不等说明做了一次替换。这个“编辑距离路径回溯”的组合在文件Diff、SQL反向生成、代码重构工具里都很实用。6. 从热题100走向面试变体One Edit Distance与易错复盘编辑距离的妙处在于它还能衍生出一系列变体题。热题100本身只收录了标准版但你刷题时一定会遇到它的兄弟们。把这些变体放在一起看你会发现它们的核心都是“利用编辑距离的状态模型针对操作集合做文章”。6.1 高频变体只允许删除、只差一次编辑、输出路径第一个高频变体是LeetCode 583两个字符串的删除操作。这题只允许删除操作求让两个字符串相等所需的最小删除次数。答案其实是用两个字符串的总长度减去2倍的最长公共子序列长度。为什么因为只允许删除可以等价为找到两个字符串中相同的最长子序列把它保留剩下的字符全部删掉。这个变体把编辑距离从“三种操作”降级为“一种操作”反而让你更清楚地看到LCS和编辑距离之间的内在联系。第二个高频变体是LeetCode 161One Edit Distance。题目要求判断两个字符串是否只差一次编辑操作。这题不需要完整跑一遍DP因为只差一次编辑意味着大部分字符顺序必须一致。用两个指针从头扫描找到第一个不同位置后跳过这个位置看剩余部分是否完全相同。如果两个字符串长度相同尝试替换如果长度相差1短的那个尝试插入一个字符。复杂度是O(n)比DP快很多。这题是编辑距离的“思想降级”用来考是否真的理解了三种操作对字符串结构的影响。第三个升级变体是输出完整编辑路径。标准解法只需要返回距离但很多公司加面时会让你把每一步操作打印出来比如insert e at position 3。做法就是上面提到的路径回溯需要在填表时额外用一个方向数组记录每个格子从哪来。面试时遇到这个变体通常意味着前面几个问题答得不错面试官在加大难度。6.2 我在Java实现里踩过的高频坑编辑距离的坑不算深但很碎。我把自己踩过、也见别人踩过的坑总结成下面几类。第一边界初始化错乱。dp[i][0]i和dp[0][j]j含义分别是“删空”和“插入空串”写反了也能跑但答案错得离谱。第二charAt索引偏移。dp的i对应word1前i个字符所以访问的是word1.charAt(i-1)写错成i就直接越界了。第三一维DP里prev的保存时机。必须先存temp再更新dp[j]谨记。第四记忆化搜索里memo数组忘记用-1初始化而是默认0会导致有些状态被误当成已经计算过而直接返回0。第五滚动数组里cur[0]忘记赋当前行的i值。第六把word1和word2搞反dp[i][j]的含义是word1变word2不是反过来的弄反后答案虽然一样但代码跟你脑中的思路对不上容易越改越乱。还有一个比较隐蔽的认知点当word1.charAt(i-1)等于word2.charAt(j-1)时dp[i][j]可以直接取dp[i-1][j-1]这没问题。但如果你写Math.min(dp[i-1][j-1], Math.min(dp[i-1][j]1, dp[i][j-1]1))结果也一样因为dp[i-1][j-1]一定小于等于另外两个加1后的值。所以有些人图省事不做字符相等的判断统一套min公式答案也是对的。但在一维DP优化时你仍然必须正确处理左上角变量不然即使字符相等也会丢失状态。6.3 调试DP的有效方法打表和对拍动态规划题写完就报错最忌讳的是盯着代码空想。我调试编辑距离时用两个方法几乎每次都能快速定位问题。第一个方法是打表。在迭代DP里填入几行后把dp数组按行打印出来拿笔手动算几个格子对比打印结果。比如word1horse、word2ros推出第一行和第二行的值后你立刻能发现初始化是否有问题、转移方向是否写反。打表代码很简单循环里加几行System.out.println或者用Arrays.deepToString(dp)输出定位完再删掉。第二个方法是对拍。先写一个绝对正确的暴力递归版本作为参照再写优化版本然后用随机生成的字符串反复调用两个版本比对输出是否一致。Java里可以写一个简单的循环随机生成长度0到10的小写字符串调用两个方法遇到不一致就打印出错用例。这个方法是排查“计算逻辑正确但实现有偏差”的利器帮我抓出过至少三次索引边界问题。这两招不仅适用于编辑距离刷所有DP题都能用。把这两个习惯内化之后你会发现动态规划调试的痛苦会少一半。最后再分享一个刷题顺序上的体会如果你正在刷力扣热题100建议把编辑距离放在刘斐波那契、爬楼梯、不同路径这类入门DP题之后刷效果会好很多。因为编辑距离集合了二维状态定义、三种方向转移、边界初始化、空间优化四个主要考点每一个考点都值得单独吃透。等你把这道题彻底拿下再去看LCS、最长回文子序列、正则表达式匹配这些题会发现它们的底层都是一套思路——定义好状态想清楚转移方向然后处理边界。热题100里的编辑距离就像一把钥匙打开的不只是这一道题而是整个二维动态规划的大门。