题目描述
给你两个单词?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 <= 500
word1 和 word2 由小写英文字母组成
题解
方法：动态规划
根据题目描述，对单词的操作一共有三种：
- 插入一个字符；
- 删除一个字符；
- 替换一个字符。
而对于两个单词A、B就有6种操作，但是，我们发现：
- 对单词A删除一个字母 等价于 对单词B插入一个字母；
- 对单词A插入一个字母 等价于 对单词B删除一个字母；
- 对单词A替换一个字母 等价于 对单词B替换一个字母。
这样，我们实际上只有3种不同的操作，如下：
- 在单词A插入一个字符；
- 在单词B插入一个字符；
- 修改单词A的一个字符。
我们设置一个二维数组dp[][]来存储A和B的编辑距离，其中dp[i][j]的前 i 个字母和B的前 j 个字母之间的编辑距离。
- 对于dp[i][j-1]，我们在B的末尾插入一个字符，即得到单词A，即dp[i][j] 最小可以为?dp[i][j-1] + 1；
- 对于dp[i-1][j]，我们在A的末尾插入一个字符，即得到单词B，即dp[i][j] 最小可以为?dp[i-1][j] + 1；
- 对于dp[i-1][j-1]，如果A的第 i 个字母和B的第 j 个字母相同，则dp[i][j] 最小可以为dp[i-1][j-1]；如果不同，则dp[i][j] 最小可以为?dp[i-1][j-1] + 1；
因此，我们的到以下状态转移方程：
如果A和B的最后一个字母相同：
如果A和B的最后一个字母不同：
时间复杂度：
，其中，m和n分别为word1和word2的长度。
空间复杂度：
?代码
class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length();
int m = word2.length();
int[][] dp = new int[n + 1][m + 1];
// 边界状态初始化
for (int i = 0; i <= n; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= m; j++) {
dp[0][j] = j;
}
// 计算dp值
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int cur = 0;
if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
cur = 1;
}
dp[i][j] = Math.min(dp[i - 1][j - 1] + cur, 1 + Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
return dp[n][m];
}
}