「这是我参与11月更文挑战的第4天,活动详情查看:2021最后一次更文挑战」
前言
力扣第七十二题 编辑距离
如下所示:
给你两个单词 word1
和 word2
,请你计算出将 word1
转换成 word2
**所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
复制代码
一、思路
这一题我刚开始看到的时候也是不知道从何处下手,后面也是看了题解才知道可以从 动态规划
下手。
这一题最重要的就是要知道 dp[i][j]
是 words1
的前 i
个字符到 word2
的前 j
个字符的编辑距离。
我们可以得到如下的状态转移方程:
- 若 A 和 B 的最后一个字母相同:
D[i][j] = min(D[i][j-1]+1, D[i-1][j]+1, D[i-1][j-1])
- 若 A 和 B 的最后一个字母不同:
D[i][j] = 1 + min(D[i][j-1], D[i-1][j], D[i-1][j-1])
后面就是 动态规划
中的填写二维数组的内容了,大致的步骤如下所示:
- 初始化边界内容,
dp[i][0] = i
和dp[0][j] = j
(dp[i][0] = i
相当于需要删除了i
次,dp[0][j] = j
相当于插入j
次) - 双层循环遍历,填满
dp[i][j]
- 返回
dp[word1.length][words2.length]
的值即可
图解算法
此处以 word1 = "horse", word2 = "ros"
作为例子
- 初始化边界值后,
dp[][]
如下所示
- 根据状态转移方程填充第一行
先判断 words1[i]
与 words2[j]
是否相等
- 如果相等:取
左边的值 + 1
、上边的值 + 1
、左上角的值
中的最小值作为结果 - 如果不相等:取
左边的值 + 1
、上边的值 + 1
、左上角的值 + 1
中的最小值作为结果
- 填充第二行
- 填充后续的行
- 返回右小角
dp[i][j]
的结果3
即可
二、实现
实现代码
注意:为了将
i
j
的坐标与数组对齐,在初始化二维数组时,二维数组为dp[len1 + 1][len2 + ]
/**
* 动态规划
*/
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
// 下标对齐
int[][] dp = new int[len1+1][len2+1];
// 初始化边界值
for (int i=1; i<len1+1; i++) {
dp[i][0] = i;
}
for (int j=1; j<len2+1; j++) {
dp[0][j] = j;
}
// 遍历
for (int i=1; i<len1+1; i++) {
for (int j=1; j<len2+1; j++) {
// 判断是否相等
if (word1.charAt(i) == word2.charAt(j)) {
dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]) + 1, dp[i-1][j-1]);
} else {
dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
}
}
}
return dp[len1][len2];
}
复制代码
测试代码
public static void main(String[] args) {
new Number72().minDistance("horse", "ros");
}
复制代码
结果
三、总结
感谢看到最后,非常荣幸能够帮助到你~♥
如果你觉得我写的还不错的话,不妨给我点个赞吧!如有疑问,也可评论区见~
近期评论