LeetCode 72. 编辑距离
题目描述
✅ 72. 编辑距离
题意分析
要把
word1变成与word2完全相同的字符串，每次可以插入一个字符、删除一个字符，或把一个字符替换成另一个字符，每次操作都计为1。目标是最少操作次数，不需要输出具体操作过程。插入和删除会改变字符串长度以及后续字符的位置，因此不能只统计相同下标处有多少字符不同。两个字符串也可能为空：空串变成非空串只能逐个插入，非空串变成空串则只能逐个删除。
解法一：二维动态规划
核心思路
[!blue]
直接枚举整串的编辑过程，会反复遇到“某个前缀怎样变成另一个前缀”的相同问题。定义
dp[i][j]为把word1的前i个字符变成word2的前j个字符所需的最少操作数。这里i、j是长度，两个末尾字符的下标分别是i - 1、j - 1。先考虑两个末尾字符不同的情况。为了完成这两个前缀的转换，最后处理末尾时有三种选择：
- 替换：先把源串前
i - 1个字符变成目标串前j - 1个字符，再把源串末尾改成目标字符，代价是dp[i - 1][j - 1] + 1。- 删除：删掉源串末尾字符后，剩下的前
i - 1个字符仍需变成目标的前j个字符，代价是dp[i - 1][j] + 1。- 插入：先把源串前
i个字符变成目标串前j - 1个字符，再补入目标末尾字符，代价是dp[i][j - 1] + 1。三种选择覆盖了末尾失配时的处理方式，分别取子问题的最优值，再选总代价最小的一种。如果两个末尾字符相同，可以保留这对字符而不付出新代价，问题直接缩小为两个更短前缀，得到
dp[i][j] = dp[i - 1][j - 1]。当目标前缀为空，只能删除全部
i个源字符，所以dp[i][0] = i；当源前缀为空，只能插入全部j个目标字符，所以dp[0][j] = j。其余状态只依赖左上、上方和左方，因此按行从左到右计算时，所需的较小子问题都已经求出。
解题步骤
- 设字符串长度为
m、n，创建(m + 1) × (n + 1)的状态表，把空前缀也作为合法状态。- 初始化第
0列dp[i][0] = i，以及第0行dp[0][j] = j。- 外层从
i = 1到m，内层从j = 1到n，比较两个前缀的末尾字符。- 相同时继承左上角；不同时取左上、上方、左方的最小值再加
1。- 返回
dp[m][n]，它恰好对应两个完整字符串的转换。
代码实现
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int 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++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 三个前驱依次代表替换、删除源字符、插入目标字符。
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
}
return dp[m][n];
}
}
func minDistance(word1, word2 string) int {
m, n := len(word1), len(word2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
// 目标为空前缀时，只能逐个删除源字符。
dp[i][0] = i
}
for j := 0; j <= n; j++ {
// 源为空前缀时，只能逐个插入目标字符。
dp[0][j] = j
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
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-1], dp[i-1][j], dp[i][j-1])
}
}
}
return dp[m][n]
}
复杂度分析
- 时间复杂度：$O((m+1)(n+1))$，包含空前缀边界的初始化和全部状态转移。
- 空间复杂度：$O((m+1)(n+1))$，保存包含空前缀边界的二维状态表。
关键点总结
[!green]
- 状态描述两个前缀之间的最少编辑次数，不能只记录某一边处理到哪里。
- 替换同时消耗两边末尾，删除只消耗源串末尾，插入只消耗目标串末尾，这决定了三个状态来源。
- 相同末尾可以直接保留，空前缀则决定递推的初始边界。
解法二：滚动数组动态规划
核心思路
[!blue]
二维递推只使用上一行的同列、上一行的左邻列和当前行的左邻列，更早的行计算完便不再需要。因此可以复用一行数组，省去完整状态表，但必须区分每个值是否已经被本行覆盖。
更新第
i行第j列之前，dp[j]还是上一行同列的值，对应删除；dp[j - 1]已经是当前行左侧的值，对应插入。左上角旧值已经被覆盖，所以额外用pre保存，它对应字符相等时的直接继承，或字符不等时的替换。每列先令
up = dp[j]保留上方旧值，再按原递推更新dp[j]，最后令pre = up。对下一列而言，本列原来的上方值恰好就是它的左上角。这个顺序保证所有来源都与二维算法一致。每行开头也要按同样顺序处理边界：先把旧
dp[0]存入pre，再令dp[0] = i。另外，插入和删除费用相同，反向转换的最少操作数也相同，因此可以交换两个输入，把较短字符串放在列方向，让数组长度最小。
解题步骤
- 若
word2更长，交换两个字符串，让它成为较短的一侧。- 创建长度为
word2.length + 1的数组，令dp[j] = j，表示二维表的第0行。- 每行开始先保存
pre = dp[0]，再把dp[0]更新为当前源前缀长度i。- 从左向右遍历各列。先保存
up = dp[j]；末尾相同则令dp[j] = pre，否则令其等于min(pre, up, dp[j - 1]) + 1。- 计算完本列后执行
pre = up，全部行处理完后返回数组最后一项。
代码实现
class Solution {
public int minDistance(String word1, String word2) {
if (word1.length() < word2.length()) {
String temp = word1;
word1 = word2;
word2 = temp;
}
int[] dp = new int[word2.length() + 1];
for (int j = 0; j < dp.length; j++) {
dp[j] = j;
}
for (int i = 1; i <= word1.length(); i++) {
// 先保留上一行的空前缀状态，再更新当前行的边界。
int pre = dp[0];
dp[0] = i;
for (int j = 1; j <= word2.length(); j++) {
// 当前列旧值是上方状态，覆盖前必须保存。
int up = dp[j];
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[j] = pre;
} else {
dp[j] = Math.min(pre, Math.min(up, dp[j - 1])) + 1;
}
// 下一列需要的旧对角线，就是本列覆盖前的上方值。
pre = up;
}
}
return dp[word2.length()];
}
}
func minDistance(word1 string, word2 string) int {
if len(word1) < len(word2) {
word1, word2 = word2, word1
}
dp := make([]int, len(word2)+1)
for j := range dp {
dp[j] = j
}
for i := 1; i <= len(word1); i++ {
// 先保留上一行的空前缀状态，再更新当前行的边界。
pre := dp[0]
dp[0] = i
for j := 1; j <= len(word2); j++ {
// 当前列旧值是上方状态，覆盖前必须保存。
up := dp[j]
if word1[i-1] == word2[j-1] {
dp[j] = pre
} else {
dp[j] = min(pre, up, dp[j-1]) + 1
}
// 下一列需要的旧对角线，就是本列覆盖前的上方值。
pre = up
}
}
return dp[len(word2)]
}
复杂度分析
- 时间复杂度：$O((m+1)(n+1))$，包含空前缀处理，每个前缀组合计算一次。
- 空间复杂度：$O(\min(m,n)+1)$，滚动数组按较短字符串分配，并保留空前缀位置。
关键点总结
[!green]
- 一维写法没有改变状态转移，只是让不同位置轮流保存上一行或当前行的值。
- 内层必须从左向右，才能读取已经更新好的当前行左侧状态。
- 每一列都要在覆盖前保留旧值，下一列才有正确的左上角；每一行也要更新空前缀边界。
易错点总结
[!yellow]
- 把状态下标当作字符下标会错位或越界；
dp[i][j]的末尾字符应读取i - 1、j - 1。- 首行首列不能全部置零，它们分别需要插入或删除相应数量的字符。
- 插入的来源是当前行左侧，删除的来源是上一行同列，不能把两个来源都理解成同时缩短字符串。
- 滚动更新时若先覆盖
dp[j]再保存给pre，下一列读到的就是本行新值，不再是旧对角线。- 只把滚动数组的
dp[0]初始化一次不够；每行的源前缀长度不同，删除到空串的代价也不同。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 161. 相隔为 1 的编辑距离 | 中等 | 把允许编辑次数限制为恰好1后，可根据长度关系双指针处理，无需完整二维DP。 |
| 583. 两个字符串的删除操作 | 中等 | 原题只允许删除，最优值可由最长公共子序列推导，本题还允许插入和替换。 |
| 1143. 最长公共子序列 | 中等 | 用两个前缀构成二维动态规划状态；本题允许插入删除替换并求最小代价，该题求最长公共子序列长度。 |
| 712. 两个字符串的最小ASCII删除和 | 中等 | 用两个前缀构成二维动态规划状态；本题允许插入删除替换并求最小代价，该题删除代价改为字符编码之和。 |
| 补充题 178. 带权编辑距离 | 中等 | 都用插入、删除、替换三种转移计算编辑距离；补充题分别设置操作费用。 |