编辑距离详解：从LeetCode 72到动态规划与真实应用

编辑距离这道题刷过LeetCode的人应该都不陌生——就是那个经典的“从word1变到word2最少需要多少步操作”操作只有三种插入、删除、替换。标题里的“单词间转换的最小次数leetcode72”说白了就是这道题。很多第一次接触的人会被“最小次数”这四个字吓住感觉像是某种贪心或者搜索问题。实际上它是一道非常典型的动态规划入门题而且这道题的价值远不止“AC一道题”这么简单编辑距离思想在拼写纠错、搜索引擎模糊匹配、基因序列对比、OCR识别纠错这些真实场景里都在用。这篇文章我想从一个刷题老手加实际用过的角度把这道题从原理到代码到坑位完整拆一遍。不管你是刚开始刷DP的小白还是想把这题背后的优化思路摸透这篇都能给你一点参考。1. 题目本质与设计思路拆解1.1 编辑距离到底在算什么先把题面说清楚。给定两个单词word1和word2允许三种操作插入一个字符删除一个字符替换一个字符问从word1转换成word2最少需要几步。比如horse到ros答案是3。很多人看到这个第一反应是“我能不能直接找相同字符挨个比对”或者“是不是跟最长公共子序列有关系”。确实有关系但不是一回事。最长公共子序列LCS只考虑字符顺序不变的情况下能保留多少个公共字符而编辑距离里还有一个替换操作替换一次算一步比“删除插入”两步要省。所以单纯用“总长度减两倍LCS”这种思路算出来的不是最小编辑次数除非题目限定只能增删不能替换。这题的另外一个迷惑点在于三个操作看起来简单实际上组合起来是爆炸性的。word1长度稍微一长暴力枚举所有操作序列就完了。所以必须找一个结构化的方法把大问题拆成小问题这就是动态规划出场的时机。1.2 为什么能拆成子问题编辑距离能拆核心是“对word1的第i个字符做操作时前面i-1个字符已经搞定了”。你可以想象成一个人拿着一串字符慢慢改每次只看当前字符如果和word2对应位置一样就跳过不一样就得在“删掉它”“替换它”“在它前面插一个字符”三个动作里选一个选的依据是后面要做的代价最小。反过来说我们并不关心这中间具体是哪一步删了哪个字符只关心“word1的前i个字符变成word2的前j个字符最少要多少步”。这个子问题的答案一旦算出来再往后推一格就是看第i1个字符和第j1个字符的状态。这种从小到大的递推天然适合用二维数组来填。这里有个很多初学者绕不过去的弯为什么插入操作要看dp[i][j-1]而不是dp[i-1][j]打个比方你手里有一串积木要搭成另一串形状。如果发现当前最后一块积木对不上你的选择不是只盯着这一块而是要想想“是不是应该在当前这块后面补一块新的”。插入了新的一块之后你原来的积木还剩下“前i块”但是目标形状已经被你匹配到了“前j-1块新插入这块”。所以插入操作对应的子问题是“用word1前i个字符去匹配word2前j-1个字符”然后加一次插入代价。这个逻辑一旦理顺整个状态转移方程就顺了。2. 动态规划核心细节解析2.1 状态定义与表格设计定义dp[i][j] 将word1的前i个字符转换成word2的前j个字符所需的最少操作次数。这里的边界非常关键dp[0][j] jword1为空串要得到word2前j个字符只能靠j次插入dp[i][0] iword2为空串要清空word1前i个字符只能靠i次删除为什么要单独把这两行一列拎出来因为动态规划的递推必须从某个确定的值开始空串对任意字符串的距离是最简单、最确定的。很多人在做题时或者面试手写时栽跟头都是因为忘了这两个初始条件或者把dp[0][j]设成了0。那样递推出来的整个表格全是错的。填表时从左到右、从上到下依次递推最终答案就是dp[m][n]m和n分别是两个单词的长度。画一个二维表出来你会发现其实这张表就是“把一个字符串逐步变成另一个字符串”的代价地图。横向表示目标字符串增长纵向表示源字符串减少中间每个格子表示一个中间状态。2.2 状态转移方程逐项拆解对于dp[i][j]i≥1, j≥1先看word1[i-1]和word2[j-1]这两个字符下标要减一因为dp的下标从1开始计数如果相等dp[i][j] dp[i-1][j-1]如果不相等dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])很多人不理解为什么字符相等时就直接抄左上角的值不用考虑“删了再插”之类的问题。因为既然两个字符一样它们本身不需要任何操作来转换。你只需要管好各自的前缀。这里有一个容易被忽略的细节字符相等时也可能存在“删掉当前这个字符再去匹配”的方案但这种方案至少是1次操作而直接保留它是0次操作所以不可能是最优解。因此相等时直接等于左上角是安全的。再看不相等的三个选择删除操作dp[i-1][j] 1。语义是“word1前i-1个字符已经能变成word2前j个字符了那我干脆把word1的第i个字符删掉”。相当于把当前这个碍事的字符去掉问题回到更短的字符串。插入操作dp[i][j-1] 1。语义是“word1前i个字符已经能变成word2前j-1个字符了那我再在末尾插入一个字符补齐第j位”。插入的字符就是word2[j-1]。替换操作dp[i-1][j-1] 1。语义是“word1前i-1个字符已经能变成word2前j-1个字符了我只要把第i个字符替换成word2的第j个字符”。这三个里取最小再带上当前这一步的代价1就是当前格子的值。2.3 为什么要用min而不是直接贪心这一步也是很多人的疑问既然每次只要选代价最小的操作就行了为什么不能按贪心策略一步步走因为局部最优不等于全局最优。举个简单的例子word1abcword2ab。贪心看最后一个字符c执行删除得到ab只需要1步。但如果word1abcword2axc贪心可能想先把b替换成x这一步需要1步然而你如果先删掉b再插入x总共要2步。两种做法代价不同取决于前面已经完成的匹配情况。只有把所有可能路线的代价都放在dp表格里从全局最小去推才能保证结果是最小的。这里可能有人会说“替换通常比删除插入更省那默认选替换不就行了吗”不一定。比如word1abcword2db比较第三个字符c和b时如果你把c替换成b得到abb还要处理前面的问题但如果你直接把c删掉得到ab再考虑怎么把ab变成db可能总代价更小。所以三个方向必须都算然后取最小值不能偷懒。3. 实操实现与核心代码讲解3.1 最基础的高维DP实现先把最朴素的二维DP版本写出来这个版本时间复杂度和空间复杂度都是O(mn)。虽然空间可以优化但对理解题意最重要。def minDistance(word1: str, word2: str) - int: m, n len(word1), len(word2) # 创建 (m1) x (n1) 的二维数组 dp [[0] * (n1) for _ in range(m1)] # 初始化边界 for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j # 填表 for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min( dp[i-1][j], # 删除 dp[i][j-1], # 插入 dp[i-1][j-1] # 替换 ) return dp[m][n]代码本身不长但有几个细节值得注意。第一dp数组的尺寸是(m1)x(n1)多出来的一行一列就是给空串状态留的。如果两个单词都为空dp[0][0] 0直接返回0逻辑也正确。第二遍历顺序必须是i从1到m、j从1到n。因为dp[i][j]依赖dp[i-1][j]上一行、dp[i][j-1]同一行前一列、dp[i-1][j-1]左上角。只要一行一行往下填这三个位置一定都已经算好了。第三很多人纠结的地方在于为什么word1 horse, word2 ros时结果是3。手动填一遍初始化第0行和第0列第1行第1列h vs r不相等取min(1,1,0)11第1行第2列h vs o不相等取min(2,1,1)12一路填下来最终dp[5][3]3这个过程建议新手亲手在纸上画一遍比看十遍讲解都有用。画表格的过程中你会直观地看到“删除”“插入”“替换”这三个方向是怎么反映在格子上的。3.2 空间优化从二维压到一维上述版本在LeetCode能直接过但如果面试官追问“能不能把空间复杂度降到O(n)”你得会写。这时候要用滚动数组。仔细观察可以发现dp[i][j]只依赖当前行的左边dp[i][j-1]、上一行的当前位置dp[i-1][j]、以及上一行的左边dp[i-1][j-1]。也就是说我们不需要保留整个二维表格只需要保留一行就够了。但有个麻烦dp[i-1][j-1]在更新时会丢失。所以必须在更新前把旧值存下来。def minDistance_optimized(word1: str, word2: str) - int: m, n len(word1), len(word2) dp list(range(n1)) # 初始化 dp[0][j] j for i in range(1, m1): prev dp[0] # 相当于 dp[i-1][0] dp[0] i # 相当于 dp[i][0] i for j in range(1, n1): temp dp[j] # 保存旧的 dp[i-1][j] if word1[i-1] word2[j-1]: dp[j] prev # 相当于 dp[i-1][j-1] else: dp[j] 1 min( dp[j], # 删除dp[i-1][j] dp[j-1], # 插入dp[i][j-1] prev # 替换dp[i-1][j-1] ) prev temp # 下一次循环时prev就是旧的 dp[i-1][j-1] return dp[n]这里最容易踩的坑有两个prev的更新顺序。每次内层循环结束后必须把temp即旧的dp[j]赋给prev。如果忘了后续计算的prev就不是上一行的左上方格子了。字符串下标和数组下标的错位。内层循环的j从1开始但字符串比较时用的是word1[i-1]和word2[j-1]。这个-1很多人写代码时容易漏一漏就是答案偏差。空间优化版本虽然省了内存但可读性确实比二维版本差。面试时建议先把二维版本讲清楚再展示优化版面试官会更容易跟上你的思路。3.3 复杂度分析与语言差异时间复杂度和空间复杂度是面试必问的点。时间双重循环显然O(mn)空间二维是O(mn)滚动数组是O(n)如果两个字符串长度差距很大我们还可以做个小的优化把短的那个作为列这样滚动数组的空间就是min(m,n)1。具体做法是如果n大于m就先交换word1和word2。因为dp表格的行列对称结果一样但内存更小。不同语言的写法有一些细节差异。Python的二维数组初始化是[[0](n1) for _ in range(m1)]别写成[[0](n1)]*(m1)后者是共享引用改一行所有行都变。C/Java则直接vectorvector dp(m1, vector (n1, 0))。JavaScript的数组稍微灵活但思路一样。这些语言层面的细节在实际写的时候影响特别大尤其是Python那个共享引用的坑几乎每个入门者都会踩一次。4. 常见问题与排查技巧实录4.1 为什么我的递归版本超时了很多初学者会先写一个递归版本类似“如果字符相等就递归处理剩余部分否则尝试三种操作取最小值”。逻辑上没问题但直接递归会有大量重复计算。比如计算dp(1,1)可能在多个分支里都被算过很多次。不加记忆化的话时间复杂度是指数级的LeetCode上直接TLE。解决方式有两种改成自底向上的DP填表保留递归但加lru_cache或备忘录数组用Python的functools.lru_cache可以很轻松给递归加缓存但面试时最好主动说明“这是记忆化搜索本质也是DP时间复杂度O(mn)”。4.2 边界条件到底怎么初始化才不出错我见过最多的错误之一是dp[0][j]初始化为0。这个错误发生在对dp含义理解不深的时候。dp[0][j]表示从空字符串变成word2的前j个字符需要多少次操作。空字符串变到任意非空字符串显然只能靠插入所以一定是j次。如果把0行全设成0那么后面所有格子都会被污染结果明显偏小。另一个边界问题是遍历范围。有人写for i in range(m)而不是range(1, m1)然后在循环体里对i-1做判断容易导致最后一个字符没处理到。建议还是沿用dp的经典写法让下标从1开始直观且不容易漏。4.3 空间优化版本结果突然不对了如果你把二维版本改成滚动数组后结果出错先检查会不会是prev这个临时变量没有正确更新。我调试时习惯在纸上列出内层循环里dp[j]和prev每一步的值比如i1, j1时prev应该保存的是dp[0][0]而dp[j]保存的是dp[i-1][j]。一个简单自测用例是word1a, word2a期望返回0。另一个是word1a, word2ab期望返回1因为只需要插入一个b。再给一个比较隐蔽的用例word1a, word2b期望返回1因为替换一次就够。如果程序返回了2说明替换分支没生效或prev取值错误。4.4 遇到内存超限怎么办在内存受限的环境下二维数组O(mn)可能撑不住。特别是两个字符串都很长的时候比如mn10000二维DP开10000x10000的数组直接内存爆掉。这时候必须用滚动数组。如果题目只是要求返回最小次数而不是重构操作路径滚动数组基本没有损失。但如果题目改成“要求打印一条具体的操作序列”就不能只留一行了因为你需要回溯整个决策过程。这种情况下要么保留完整二维表要么用额外的路径记录数组。这个区别在实际工作中也很重要很多算法题只要求判个结果但真实系统里往往需要知道“怎么变的”而不是“变了多少次”。4.5 常见误区和坑位速查表问题现象可能原因解决办法结果比预期小初始化dp[0][j]设成了0正确初始化为j结果比预期大遍历范围漏了最后一个字符使用range(1, m1)结果时对时错Python二维数组初始化用了乘法共享引用用列表推导式创建滚动数组版本结果错prev变量更新顺序不对先存temp再更新prev数组越界忘记dp比原字符串多一行一列申请(m1)x(n1)大小递归超时没有缓存重复子问题加备忘录或改迭代DP误以为替换总是最优忽略字符相等时直接保留相等时直接取左上角这个表里的每一项都是我实际踩过或者帮别人debug时遇到过的真不是吓唬人。尤其那个Python共享引用的问题我当年第一次写二维DP时也中招了排查了半天才发现每一行其实指向了同一块内存。5. 真实场景应用与扩展思考5.1 编辑距离在拼写纠错里的实际用法编辑距离不只是算法题在真实系统里是搜索引擎和文本编辑器的基础工具。比如你在软件里输入一个单词系统提示“您是不是想输入xxx”背后常用的一种做法就是计算用户输入和词典里每个单词的编辑距离取距离最小的前几个作为候选。那这里有个性能问题词典可能有几十万个单词总不能每输入一个词就全量算一遍。实际工程里通常的做法是先用开头字母、长度等条件粗过滤缩小候选集再对候选集算编辑距离。还有一些优化手段叫BK树或n-gram索引把编辑距离用作度量来建树查找时就能剪枝。5.2 DP之外限制编辑距离的快速判断有一类应用只关心“编辑距离是否小于等于某个阈值”比如容错匹配里经常说“允许1个字符错误”。这时候不需要把完整的DP表算完可以用一个剪枝技巧如果当前行最小可能代价已经超过阈值k直接跳过这行。这种做法在模糊匹配里很常用比如DNA序列里允许少量变异的搜索。这种“只算对角带”的优化本质上利用了编辑距离的一个性质当i和j相差超过k时dp[i][j]至少是|i-j|而|i-j|已经大于等于k就没必要继续算了。虽然LeetCode 72原题不考这个但面试时你主动提一句会显得你不仅会做题还懂优化。5.3 变体问题允许更多操作时怎么办编辑距离的经典版本只有三种操作。真实场景里可能有额外的操作比如允许交换相邻两个字符transposition这在自然语言处理里非常常见因为人类打字时经常把两个相邻字符打反了。如果允许交换操作状态转移方程就需要额外考虑dp[i-2][j-2]这种跨格子的情况。LeetCode里有一道题就是比“单词拆分”更复杂的版本但很多扩展题型的思想都是在这个基础DP上加状态。所以搞懂72题对你刷其他编辑距离变体非常有帮助。5.4 从编辑距离到文本相似度计算编辑距离本身也可以作为文本相似度的度量指标也就是1 - 编辑距离/最大长度。这个值经常被用在“某系统上报的地址和标准地址是否匹配”这类场景。不过编辑距离有局限性它只关注字符级别的差异不考虑单词顺序、语义等因素所以在大段文本对比时效果不一定好。这时可以考虑基于词向量的语义相似度或者基于最长公共子序列的相似度算法。但这题给你打下的“把字符串差异量化”的思维框架在任何相似度算法里都能用上。5.5 工程里注意的边界场景真实系统里字符串可能非常长也可能有空串、纯Unicode字符、大小写差异、空格差异。编辑距离对这些情况都敏感。实际做数据清洗时我经常先做标准化转小写、去空格、统一全半角再算编辑距离否则结果会偏离预期。另一个工程化的细节是编辑距离对长短不一的字符串特别敏感。比如两个地址一个是“北京市朝阳区xxx路1号”另一个是“北京市朝阳区xxx路1号A座”虽然只差3个字符但按编辑距离是3可是从语义上讲两个地址几乎一样需要额外用长度归一化后的相似度来判断。这些实际经验正是算法题和真实业务之间的鸿沟。我个人在实际操作中的体会是LeetCode 72这道题特别适合做动态规划的“定海神针”它不像背包问题那样抽象难懂又有足够的变体空间去考察你对状态、边界、优化的理解。如果你能把这道题从二维DP写到滚动数组再把状态转移的每一个语义都用白话说清楚那以后再遇到“字符串变化”类的题目你就知道怎么下手了。最后再分享一个小技巧面试或者写题如果卡壳了就在草稿纸上画一张dp表格把第一行第一列填好然后一格一格往里填——这个方法帮我理清过很多思路比光盯着代码干想有效得多。