从做字符串匹配的日常需求出发，我几乎每天都会碰到"两个文本到底有多像"这类问题。早年用暴力逐个字符比对，效率低还容易误判，后来接触到了编辑距离这个思路，一下子把模糊匹配、拼写纠错、文本查重这些场景统一到了一个公式框架下。LeetCode 72题就是最经典的那道"编辑距离"（Edit Distance），也是动态规划入门里绕不开的硬骨头。它要求计算把一个字符串变成另一个字符串所需的最少编辑操作次数，操作只有三种：插入、删除、替换。这篇文章我打算把这道题从直觉、递推、表格推演到代码落地、空间优化、实际工程应用完整拆一遍，适合正在刷题准备面试的同学，也适合想在项目中用模糊匹配但又不知道从哪下手的开发者。
1. 从"两个字符串有多像"说起：编辑距离到底在算什么
1.1 编辑操作的定义：插入、删除、替换
编辑距离最初由一位苏联学者在1965年提出，所以它也叫莱文斯坦距离（Levenshtein distance）。它的核心定义特别朴素：给定两个字符串s和t，允许你对s做三种操作，问最少操作几次能让s变成t。
三种操作分别是：
- 插入：在任意位置插入一个字符
- 删除：删除任意位置的一个字符
- 替换：把任意位置的字符换成另一个字符
这里有个容易忽略的细节：每一种操作都只算一次代价，也就是每次操作计1。替换一个字符如果是不同的字符，代价是1；如果字符相同，替换就没有意义，代价为0。这样一个距离定义天然具备对称性和三角不等式的近似性质，所以它很适合做"相似度"的度量。
1.2 一个不直观的例子：为什么只看"最少操作次数"
我们拿经典的"kitten"到"sitting"来感受一下。直观上这两个词很像，前三个字符只有第一个不同，但真实的最少编辑距离是3：
- kitten -> sitten（把k替换成s）
- sitten -> sittin（把e替换成i）
- sittin -> sitting（末尾插入g）
为什么不是直接数不同字符的个数？因为"不同字符个数"只考虑了替换，完全没考虑增删对字符串结构的影响。举个更极端的例子：""空字符串变成"abc"，不同字符个数根本没法算，但编辑距离很清楚——需要3次插入。这就是编辑距离比海明距离更通用的原因：它不管字符串长度是否一致，都能给出有意义的距离值。
2. 从暴力递归到记忆化：为什么盲目递归注定超时
2.1 朴素递归的直觉与指数爆炸
凡是动态规划题，最自然的起点都是写递归。对于编辑距离，从两个字符串的末尾往前看：如果我最后一步是想让s[i]和t[j]对齐，那么可能的情况只有三种：
- 已经对齐了s前i-1个和t前j-1个，最后看s[i]和t[j]是否相等，不等就替换
- 已经对齐了s前i-1个和t前j个，说明s[i]是被删除的字符
- 已经对齐了s前i个和t前j-1个，说明t[j]是靠插入得到的
于是递归式就写出来了。这种写法本质上是把一个大问题拆成三个子问题，但缺点非常明显：s和t的每个位置组合都可能被反复计算，调用树呈指数级膨胀。我试过用s="abcdefghij", t="jihgfedcba"跑朴素递归，机器直接卡死，连终端都半天没反应。两个长度只有10的字符串，递归分支就已经到了天文数字，更别说LeetCode上的测试数据长度能到几百。
2.2 记忆化搜索：先解决重复计算，再谈状态设计
在写DP表格之前，有一个折中方案叫记忆化搜索。它本质上还是递归，但加了一个缓存表，每个(i, j)组合只计算一次，后面再遇到直接查缓存。这样时间复杂度从指数级降到O(mn)，和动态规划完全一致，只是实现方式不同。
这里我特别想提醒一点：递归转记忆化不是"加了缓存就万事大吉"。Python里如果递归深度超过1000，默认会报RecursionError，两个长度500的字符串就可能触发。所以工程上我更推荐直接用自底向上的DP循环，既没有递归栈溢出风险，代码也更容易做空间优化。不过理解记忆化搜索仍然很有价值，因为它的状态定义方式和二维DP完全同构，能帮你确认自己有没有想清楚状态转移。
3. 二维DP表的核心推演：状态定义与转移方程
3.1 dp[i][j]的含义与初始化边界
动态规划的第一要义是搞清楚状态数组每个格子代表什么。对编辑距离，我建议这样定义：
dp[i][j] 表示 s 的前 i 个字符，变换到 t 的前 j 个字符，所需要的最少编辑次数。
注意这个定义里i和j都是"前缀长度"，不是下标。这是个约定俗成的设计，好处是天然处理空串情况。初始化就变得非常直观：
- dp[0][j] = j，因为空字符串要变成前j个字符，只能一直插入j次
- dp[i][0] = i，因为前i个字符要变成空串，只能一直删除i次
这个边界是很多人写错的重灾区。如果你定义dp[i][j]时把i和j当成下标而不是前缀长度，后面初始化就会乱套，索引还容易越界。我习惯在代码里先用一个m和一个n变量存长度，然后开(m+1)行、(n+1)列的二维数组，就是为了让边界条件写起来不别扭。
3.2 三种操作的转移逻辑：从"最后一步"倒推
状态转移是这道题的核心。考虑dp[i][j]这个格子，我们从s的前i个字符到t的前j个字符，最后一步操作无非三种：
第一种是删除：我先让s的前i-1个字符完成变换，变成t的前j个字符，然后删掉s的第i个字符。操作数是dp[i-1][j] + 1，因为这次删除额外花了一次操作。
第二种是插入：我先让s的前i个字符完成变换，变成t的前j-1个字符，然后插入t的第j个字符。操作数是dp[i][j-1] + 1。
第三种是替换或不动：我先让s的前i-1个字符完成变换，变成t的前j-1个字符，然后处理s的第i个字符和t的第j个字符。如果它们相等，不需要操作，就是dp[i-1][j-1]；如果不等，需要一次替换，就是dp[i-1][j-1] + 1。
最后取三种里的最小值。用公式写出来就是：
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (s[i-1] == t[j-1] ? 0 : 1))
3.3 手推一张表：以"horse"到"ros"为例
光讲公式抽象，我觉得还是得拿实例走一遍。LeetCode 72的官方示例就是s = "horse"，t = "ros"，答案是3。我建议你拿起笔，在纸上画一个6行4列的表格，先填第一行和第一列。
第一行表示"空字符串变到r、ro、ros"需要1、2、3次插入，所以填1、2、3。第一列表示"h变成空串、ho变成空串、hor变成空串..."是逐字删除，分别填1、2、3、4、5。填好边界后，按行从上往下、从左往右填，每个格子都套用上面的转移公式。
我们快速推几个关键格子：
- dp[1][1]：h变成r，min(0+1删除, 1+1插入, 0+1替换) = 1
- dp[2][2]：ho变成ro，删除支路是dp[1][2]+1=2+1=3，插入支路是dp[2][1]+1=2+1=3，替换支路取字符o等于o，代价dp[1][1]+0=1，所以结果是1
- dp[3][3]：hor变成ros，这一步推出来是2，因为在"ho变ro"的基础上，最后r和s不同，替换就是2
- 一直推到dp[5][3]，答案是3
这个手推过程比任何语言描述都有用。我当时学这道题就是靠一遍遍推表格，把"删除、插入、替换"三个方向在格子上的对应关系彻底搞明白，后面写代码就再也没犹豫过。
4. 代码落地与空间优化：从O(mn)到O(n)
4.1 标准的二维DP实现
理解了表格推演，写二维DP就只是翻译公式。下面是我在Python里最常写的版本：
def minDistance(s: str, t: str) -> int: m, n = len(s), len(t) # dp[i][j] 表示 s 前 i 个字符变成 t 前 j 个字符的最少操作数 dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if s[i - 1] == t[j - 1]: cost = 0 else: cost = 1 dp[i][j] = min( dp[i - 1][j] + 1, # 删除 s[i-1] dp[i][j - 1] + 1, # 在 s 中插入 t[j-1] dp[i - 1][j - 1] + cost # 替换或不动 ) return dp[m][n]这段代码的时间复杂度是O(mn)，空间复杂度是O(mn)。如果你只是刷题，这样提交就能过。但面试官通常不会就此收手，下一步一定会问：能不能把空间省下来？
4.2 滚动数组：为什么只用两行就够
观察转移公式，你会发现dp[i][j]只依赖三样东西：左边的dp[i][j-1]、上边的dp[i-1][j]、左上角的dp[i-1][j-1]。也就是说，计算当前行时，我只需要上一行的数据，更早的行用完就可以扔掉。
于是可以用一个只有两行的二维数组，用cur[j]表示当前行，prev[j]表示上一行。每算完一行，把cur复制给prev。这就是滚动数组优化，空间复杂度降到O(n)。
def minDistance(s: str, t: str) -> int: m, n = len(s), len(t) prev = list(range(n + 1)) # 第 0 行：空串到 t 的前 j 个字符 curr = [0] * (n + 1) for i in range(1, m + 1): curr[0] = i # 当前行第 0 列：s 前 i 个字符变成空串 for j in range(1, n + 1): cost = 0 if s[i - 1] == t[j - 1] else 1 curr[j] = min( prev[j] + 1, # 删除 curr[j - 1] + 1, # 插入，注意用的是当前行的左边 prev[j - 1] + cost # 替换或不动 ) prev, curr = curr, prev return prev[n]这里有个隐蔽的坑：插入操作用的是curr[j-1]，也就是当前行已经算出来的那个值，而不是prev[j-1]。因为"让s的前i个字符变成t的前j-1个字符，再插入t[j-1]"，这个方案建立在当前行左边格子的基础上。我第一次写滚动数组就栽在这儿，一直用prev[j-1]当插入支路，结果答案怎么都对不上，后来把一个中间状态打印出来才看出问题。
4.3 单数组极致优化：一维数组怎么处理左上角
既然只用到了上一行和当前行，你能不能干脆只用一个数组？可以，但要注意左上角的值会被覆盖，需要用一个临时变量提前存下来。我实测过这种写法，代码更短，但要维护的临时变量很容易把人绕晕，面试时如果表达不清楚，反而容易扣分。
单数组版本的思路是：当我们要更新dp[j]时，数组里原来的d[j]是"上一行第j列"，原来在d[j-1]的是"当前行第j-1列"，而上一次循环保留下来的temp是"上一行第j-1列"。稍不留神就会把方向搞混。我的建议是：面试中优先讲滚动数组（清晰且足够优），有时间再补充单数组作为进阶方案，展示你理解得更深。
5. 编辑距离的真实战场：从拼写纠错到DNA比对
5.1 拼写纠错与模糊搜索中的阈值判定
很多搜索引擎、IDE的拼写提示，底层都有一层编辑距离计算。用户敲了"helo"，词库里有"hello"、"help"、"hero"，编辑距离分别是1、2、2，系统把距离最小的"hello"排在最前面。实际工程里不会对所有词库跑完整DP，而是配合前缀树或BK树做剪枝，因为词库可能百万级，全量计算O(mn)太奢侈。我在一个小工具项目里试过，5000词的词库全量计算一次才几十毫秒，但到10万词以上就明显吃力了，后来做了分桶和长度过滤，效率提升非常明显。
5.2 DNA序列比对中的相似度概念
编辑距离在生物信息学里对应的是全局序列比对问题。DNA序列可以看作由A、T、C、G四个字母组成的字符串，插入、删除、替换对应生物学术语gap、gap和mismatch。两条序列的编辑距离越小，说明它们在进化上可能越接近。实际比对时还会引入打分矩阵，比如替换的代价不一定都是1，嘌呤和嘧啶之间的转换与颠换代价不同，这就要给每种替换单独定权重，比LeetCode 72的均匀代价复杂得多。
5.3 面试追问变种：替换代价不同怎么办，允许交换怎么办
面试官很喜欢在编辑距离上做变体。最常见的两个：
第一个是把替换代价改成2，插入删除代价还是1。这本质上只是把转移方程里的cost从0/1改成0/2，其他逻辑完全不变。
第二个是问"如果允许一次相邻字符交换也算一次操作，怎么做"。这就是经典的Damereau-Levenshtein距离，状态设计会复杂很多，因为交换操作可能依赖i-2和j-2的状态。我在真实面试中被问过这个变体，当时因为时间仓促没写完整，但把思路讲清楚了：当s[i-1]==t[j-2]且s[i-2]==t[j-1]时，可以在dp[i-2][j-2]基础上加1，还要排除连续交换造成的重复计数。这个细节如果不推演，很容易答错。
6. 实操经验与易错点总结
6.1 边界条件与索引错位：九成bug的来源
我在LeetCode上提交这道题的历次错误记录里，几乎全是边界问题。最典型的有三类：
- 初始化时把dp[i][0]=i写成dp[i][0]=0，导致空串变换结果全错
- 比较字符时用了s[i]和t[j]，但此时i和j已经是前缀长度，应该用s[i-1]和t[j-1]
- 忘记处理s或t为空串的情况，虽然dp数组本身天然支持，但如果提前判断len(s)==0直接返回len(t)，代码更清晰
6.2 递推方向不能反：为什么必须从小到大
编辑距离的状态依赖是从小索引到大索引的，所以外层循环必须从小到大遍历i和j。如果你试图从大到小推，dp[i][j]依赖的dp[i-1][j]还没算出来，结果就是错的。这一点对理解了"前缀长度"定义的人来说挺自然，但如果只背代码没理解含义，笔试时一紧张就可能写反。
6.3 实际工程中的性能取舍
刷题O(mn)能过，但真实生产环境里两个几千字符的长文本做全量编辑距离，可能会卡几百毫秒甚至更久。我的经验是先用长度差做一个粗筛：如果abs(m-n)已经大于预设阈值，直接判定不相似，根本不用算DP。另一个技巧是限制最大编辑距离k，只维护对角线附近的带状DP窗口，复杂度降到O(k*min(m,n))。这个优化在模糊搜索场景非常实用，我做的纠错模块就是这么干的，效果很稳。
最后再说一个我自己的体会：编辑距离这道题，刷一遍可能只是背下来，但如果你能把表格推演、滚动数组、变种扩展全部亲手写一遍，它对动态规划的理解会有一个质的提升。后来我再遇到其他字符串DP题，比如最长公共子序列、正则表达式匹配，心态明显稳了很多，因为底层都是同一套"最后一步思考法"在起作用。如果这篇文章能帮你把这道题吃透，那我觉得比单纯贴出答案有价值得多。
