72_编辑距离[MEDIUM]
约 591 字大约 2 分钟
2026-03-20
给你两个单词 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')解题思路
参考:编辑距离
- 定义状态:
dp[i][j]为将word1的前i个字母转换为word2的前j个字母所需要的最少操作数i控制word1(上下)j控制word2(左右)
- 基础情况:考虑
word1或word2为空串情况- 首行:
word1是空串时,要把word2插入 - 首列:
word2是空串时,要把word1全部删除
- 首行:
- 状态转移:
- 如果末尾字符相同,则
word1、word2规模都变小:dp[i][j] --> dp[i-1][j-1] - 如果末尾字符不同,有三种情况,取三种情况的最小值再加一:
dp[i][j] = min(插入,删除,替换) + 1- 插入:
word1尾部插入字符,使得word1末尾和word2末尾相同,word2规模变小
dp[i][j] --> dp[i][j-1]
- 删除:
word1尾部删除字符,word1规模变小
dp[i][j] --> dp[i-1][j]
- 替换:
word1尾部替换字符,使得word1末尾和word2末尾相同,word1、word2规模都变小
dp[i][j] --> dp[i-1][j-1]
- 插入:
- 如果末尾字符相同,则
Java 实现
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int dp[][] = new int[m+1][n+1];
// 初始化首列,即 word2 是空串时,要把 word1 全部删除
for (int i = 0; i <= m; i++){
dp[i][0] = i;
}
// 初始化首行,即 word1 是空串时,要按照 word2 全部插入到 word1 中
for (int i = 0; i <= n; i++){
dp[0][i] = i;
}
// 三种情况:
// 1. 插入: dp[i][j] --> dp[i][j-1]
// 2. 删除: dp[i][j] --> dp[i-1][j]
// 3. 替换: dp[i][j] --> dp[i-1][j-1]
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(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
}
}
}
return dp[m][n];
}