给你两个单词 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
,其中dp[i][j]
表示将word1
的前i
个字符转换成word2
的前j
个字符所需的最小操作次数。
- 定义二维数组
-
初始化:
- 如果
word1
或word2
为空,则只需将另一个字符串的所有字符插入或删除。例如:dp[i][0]
=i
,表示将word1
的前i
个字符转换为空字符串的操作次数,即i
次删除操作。dp[0][j]
=j
,表示将空字符串转换成word2
的前j
个字符的操作次数,即j
次插入操作。
- 如果
-
状态转移:
- 通过遍历
word1
和word2
中的每个字符,计算dp[i][j]
的值。对于每对字符(i, j)
:- 插入操作:将
word1
的前i
个字符转换成word2
的前j
个字符的操作次数,可以通过在word2
中插入第j
个字符得到,即dp[i][j-1] + 1
。 - 删除操作:将
word1
的前i
个字符转换成word2
的前j
个字符的操作次数,可以通过删除word1
中的第i
个字符得到,即dp[i-1][j] + 1
。 - 替换操作:将
word1
的前i
个字符转换成word2
的前j
个字符的操作次数,如果word1
的第i
个字符与word2
的第j
个字符不同,则需要替换,即dp[i-1][j-1] + 1
;如果相同,则不需要额外的操作,即dp[i-1][j-1]
。
- 插入操作:将
- 通过遍历
-
选择最小操作次数:
- 对于每个
(i, j)
,选择插入、删除和替换操作中的最小值来更新dp[i][j]
:
其中dp[i][j] = Math.min(w2dowm, Math.min(w2up, update));
w2dowm
是删除操作的结果,w2up
是插入操作的结果,update
是替换操作的结果。
- 对于每个
-
结果:
- 最终
dp[n][m]
即为将word1
转换为word2
所需的最小操作次数。
- 最终
public int minDistance(String word1, String word2) {
// 获取字符串word1的长度
int n = word1.length();
// 获取字符串word2的长度
int m = word2.length();
// 如果其中一个字符串长度为0,则返回另一个字符串的长度,即为插入或删除操作的次数
if (n * m == 0) {
return n + m;
}
// 创建一个二维数组dp,dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最小操作次数
int[][] dp = new int[n + 1][m + 1];
// 初始化dp数组
dp[0][0] = 0;
// 初始化第一列,即将word1的前i个字符变为空字符串所需的操作次数
for (int i = 0; i <= n; i++) {
dp[i][0] = i;
}
// 初始化第一行,即将空字符串变成word2的前j个字符所需的操作次数
for (int j = 0; j <= m; j++) {
dp[0][j] = j;
}
// 遍历字符串word1的每个字符
for (int i = 1; i <= n; i++) {
// 遍历字符串word2的每个字符
for (int j = 1; j <= m; j++) {
// w2up表示插入操作,将word1的前i-1个字符转换成word2的前j个字符,再插入一个字符
int w2up = dp[i - 1][j] + 1;
// w2dowm表示删除操作,将word1的前i个字符转换成word2的前j-1个字符,再删除word2的第j个字符
int w2dowm = dp[i][j - 1] + 1;
// update表示替换操作,将word1的前i-1个字符转换成word2的前j-1个字符,如果word1的第i个字符与word2的第j个字符不同,则需要替换
int update = dp[i - 1][j - 1];
if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
update += 1;
}
// 取三种操作中的最小值作为dp[i][j]的值
dp[i][j] = Math.min(w2dowm, Math.min(w2up, update));
}
}
// 返回将word1转换成word2所需的最小操作次数,即dp[n][m]
return dp[n][m];
}
标签:删除,距离,编辑,word1,个字符,word2,操作,Leetcode,dp
From: https://blog.csdn.net/wudi6688/article/details/140429387