编辑距离——三操作DP状态机与优化空间
编辑距离——三操作DP状态机与优化空间
适读人群：Java后端工程师、字符串DP学习者 | 阅读时长：约22分钟 | 难度：Hard
开篇故事
编辑距离是我职业生涯里遇到过最多次的Hard题——不是因为它难，而是因为它太经典。从DNA序列比对，到拼写纠错，到自然语言处理里的字符串相似度，编辑距离几乎无处不在。
我在一家电商平台工作时，有个需求：商品搜索时对用户输入做模糊匹配，把输入纠错到最相近的商品名。当时技术方案里就有编辑距离的身影。你平时用百度、搜狗输入法，输错了它会自动纠正，背后的核心算法之一就是Levenshtein距离，也就是这道题。
所以这道Hard题其实非常接地气。更关键的是，它的DP状态转移极具代表性：同一个位置需要从三个方向转移（插入、删除、替换），这个三分支的状态机模型在很多题里都会遇到。
今天我把状态机的每个分支都推导清楚，不是死背公式，而是真正理解。
一、题目解析
题号：LeetCode 72. Edit Distance
题目描述：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行以下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例：
- 输入：word1 = "horse"，word2 = "ros"，输出：3
- horse → rorse（替换h→r）
- rorse → rose（删除r）
- rose → ros（删除e）
- 输入：word1 = "intention"，word2 = "execution"，输出：5
数据范围：0 ≤ word1.length, word2.length ≤ 500
二、DP思路推导
2.1 状态定义
和LCS一样，处理两个字符串需要二维状态。
定义 dp[i][j] = 将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数
2.2 状态转移的三种操作推导
关注 word1[i-1] 和 word2[j-1]（最后一个字符）的关系：
情况一：word1[i-1] == word2[j-1]
最后一个字符已经相同，不需要任何操作处理这两个字符。
dp[i][j] = dp[i-1][j-1]情况二：word1[i-1] != word2[j-1]（三种操作，取最小）
替换（Replace）：把 word1[i-1] 替换成 word2[j-1]，那么只需要把 word1[0..i-2] 转换成 word2[0..j-2]，再做一次替换操作：
dp[i][j] = dp[i-1][j-1] + 1删除（Delete）：删除 word1[i-1]，那么问题变成把 word1[0..i-2] 转换成 word2[0..j-1]，再做一次删除：
dp[i][j] = dp[i-1][j] + 1插入（Insert）：在 word1[i-1] 后面插入一个字符使其等于 word2[j-1]，那么问题变成把 word1[0..i-1] 转换成 word2[0..j-2]，再插入一次：
dp[i][j] = dp[i][j-1] + 1
完整转移方程：
dp[i-1][j-1] if word1[i-1] == word2[j-1]
dp[i][j] =
min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 if word1[i-1] != word2[j-1]2.3 三种操作的对应关系（关键理解）
dp[i-1][j-1] + 1 → 替换：两个字符串都缩短1
dp[i-1][j] + 1 → 删除word1末尾：word1缩短，word2不变
dp[i][j-1] + 1 → 插入与word2末尾相同：word2缩短，word1不变把"插入"理解为：我往 word1 里插入一个 word2[j-1]，这个字符不需要再处理了，剩下的任务是把 word1[0..i-1] 变成 word2[0..j-2]，即 dp[i][j-1]。
Mermaid三分支状态机图：
2.4 边界条件
dp[0][j] = j：word1为空，需要插入j个字符才能变成word2的前j个字符dp[i][0] = i：word2为空，需要删除i个字符才能变成空串
2.5 DP表手工推导（horse→ros）
"" r o s
"" [ 0 1 2 3 ]
h [ 1 1 2 3 ]
o [ 2 2 1 2 ]
r [ 3 2 2 2 ]
s [ 4 3 3 2 ]
e [ 5 4 4 3 ]
dp[5][3] = 3 ✓三、解法一：基础二维DP
public class EditDistance {
/**
* 72. 编辑距离 - 基础二维DP
* 时间复杂度：O(m * n)
* 空间复杂度：O(m * n)
*/
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// dp[i][j] = word1前i字符转为word2前j字符的最少操作数
int[][] dp = new int[m + 1][n + 1];
// 边界初始化
for (int i = 0; i <= m; i++) dp[i][0] = i; // 删除i次
for (int j = 0; j <= n; j++) dp[0][j] = 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] = Math.min(
dp[i - 1][j - 1], // 替换
Math.min(
dp[i - 1][j], // 删除word1[i-1]
dp[i][j - 1] // 插入使匹配word2[j-1]
)
) + 1;
}
}
}
return dp[m][n];
}
}四、解法二：空间优化（一维滚动）
和LCS一样，可以用一维数组加prev变量来节省空间。
/**
* 72. 编辑距离 - 空间优化（一维滚动）
* 时间复杂度：O(m * n)
* 空间复杂度：O(n)
*/
public int minDistanceOptimized(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// 用较短的字符串作为列，节省空间
if (m < n) return minDistanceOptimized(word2, word1);
int[] dp = new int[n + 1];
// 初始化第0行：word1为空，需要插入j次
for (int j = 0; j <= n; j++) dp[j] = j;
for (int i = 1; i <= m; i++) {
int prev = dp[0]; // 保存dp[i-1][j-1]
dp[0] = i; // dp[i][0] = i（word2为空，删除i次）
for (int j = 1; j <= n; j++) {
int temp = dp[j]; // 保存本轮的dp[i-1][j]，下轮作为dp[i-1][j-1]
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[j] = prev; // prev是dp[i-1][j-1]
} else {
dp[j] = Math.min(prev, Math.min(dp[j], dp[j - 1])) + 1;
// prev=dp[i-1][j-1]替换, dp[j]=dp[i-1][j]删除, dp[j-1]=dp[i][j-1]插入
}
prev = temp; // 更新prev
}
}
return dp[n];
}五、解法三：打印编辑操作序列
面试中有时要求打印出具体的编辑步骤，和LCS打印路径思路相同。
/**
* 打印具体的编辑操作
*/
public void printOperations(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] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
}
}
}
// 反向回溯，记录操作
List<String> ops = new ArrayList<>();
int i = m, j = n;
while (i > 0 || j > 0) {
if (i > 0 && j > 0 && word1.charAt(i-1) == word2.charAt(j-1)) {
ops.add("保留 '" + word1.charAt(i-1) + "'");
i--; j--;
} else if (j > 0 && (i == 0 || dp[i][j] == dp[i][j-1] + 1)) {
ops.add("插入 '" + word2.charAt(j-1) + "'");
j--;
} else if (i > 0 && (j == 0 || dp[i][j] == dp[i-1][j] + 1)) {
ops.add("删除 '" + word1.charAt(i-1) + "'");
i--;
} else {
ops.add("替换 '" + word1.charAt(i-1) + "' → '" + word2.charAt(j-1) + "'");
i--; j--;
}
}
Collections.reverse(ops);
for (String op : ops) System.out.println(op);
}六、举一反三
编辑距离相关题目：
- LeetCode 583. 两个字符串的删除操作：只有删除操作，等价于 m+n - 2*LCS
- LeetCode 712. 两个字符串的最小ASCII删除和：带权重的删除
- LeetCode 97. 交错字符串：二维DP，但状态转移方向不同
编辑距离在实际中的应用：
- 拼写纠错（输入法、搜索引擎）
- DNA序列比对（生物信息学）
- 版本控制的diff算法基础
- 自然语言处理中的字符串相似度
七、踩坑实录
坑一：边界初始化忘记处理
dp[0][j] = j 和 dp[i][0] = i 是必须的，代表从空串变成对方需要的操作数。很多人只初始化了dp[0][0]=0，其余靠Java默认值0，导致结果偏小。
坑二：字符相等时写成了+1
字符相等时，dp[i][j] = dp[i-1][j-1]，不需要 +1！有人在 if 里也写了 +1，导致结果比正确答案大1。
坑三：三个操作的方向搞混
- dp[i-1][j-1] 来自"两个字符串都缩短"（替换）
- dp[i-1][j] 来自"word1缩短，word2不变"（删除word1的字符）
- dp[i][j-1] 来自"word2缩短，word1不变"（插入字符使匹配word2）
特别容易把"插入"和"删除"的方向搞反。记住：对word1来说，删除word1末尾对应dp[i-1][j]；插入使匹配word2末尾，等价于word2缩短，对应dp[i][j-1]。
坑四：空间优化时prev更新时机
一维优化里，prev必须在更新dp[j]之后更新为 temp（旧的dp[j]）。如果在更新dp[j]之前把 prev 改掉，就用了错误的 dp[i-1][j-1]。
八、总结
编辑距离是字符串DP里最重要的题目之一，三分支状态机是其核心：
| 操作 | 状态转移 | 语义 |
|---|---|---|
| 替换 | dp[i-1][j-1]+1 | 两个字符串末尾都处理 |
| 删除word1末尾 | dp[i-1][j]+1 | word1缩短，word2不变 |
| 插入与word2末尾匹配 | dp[i][j-1]+1 | word2缩短，word1不变 |
掌握了编辑距离，LCS和编辑距离放在一起，二维字符串DP就基本通了。