动态规划困难1 种解法
#72编辑距离
计算把 word1 转换为 word2 所需的最少插入、删除或替换次数。
#字符串#动态规划
原题
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
解题主线
- dp[i][j] 表示 word1 前 i 个字符转换为 word2 前 j 个字符的最少操作数。
- 末字符相同则直接继承 dp[i - 1][j - 1]；否则从替换、删除、插入三个前驱状态中取最小值再加一。
- 额外的第 0 行和第 0 列表示空串，使边界分别初始化为连续插入和连续删除的次数。
解法 1：二维前缀动态规划
按前缀长度从小到大填表，为每对前缀选择末字符匹配或三种编辑操作中的最优转移。
-
时间复杂度： O(mn)，m、n 分别为两个字符串长度
-
空间复杂度： O(mn)
final class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
throw new IllegalArgumentException("words must not be null");
}
int m = word1.length();
int n = word2.length();
// dp[i][j] 表示两个长度分别为 i、j 的前缀之间的最小编辑次数
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 {
// 三个前驱分别对应替换、删除 word1 末字符和插入目标末字符
int replace = dp[i - 1][j - 1];
int delete = dp[i - 1][j];
int insert = dp[i][j - 1];
dp[i][j] = Math.min(replace, Math.min(delete, insert)) + 1;
}
}
}
return dp[m][n];
}
}边界与易错点
- 字符串下标是 i - 1、j - 1，而 DP 下标是前缀长度 i、j，不能混用。
- dp[i - 1][j] 对应删除 word1 末字符，dp[i][j - 1] 对应向 word1 插入 word2 末字符。
- 两个末字符相等时不需要加一，否则会高估答案。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/zhard/Q072_char_distance.java