583. 两个字符串的删除操作
关键点1:dp数组的含义
dp[i][j],使得以i-1为结尾word1 和 以j-1为结尾的word2 相同所需的最小步数;
关键点2:递归公式的推导
if(nums1[i-1] == nums2[j-1]),则i和j同时移动,所以为i-1,j-1;dp[i][j] = dp[i-1][j-1];由于不需要进行删除操作,所以不需要加1
如果不相等:则有三种情况
情况1:i不退,j往前退一步 (操作加1)//删除单词2的字母
情况2:i往前退一步,j不退(操作加1)// 删除单词1的字母
情况3:i,j都往前退一步(操作加2)// 两个单词的字母都删除
关键点3:dp数组初始化
需要对最左边那列和最上面那行进行初始化
dp[i][0] = dp[i-1][-1]:表示单词1不是空,单词2是空的情况下,单词1要与单词2相同所需的最小删除步数,所以初始化为i
dp[0][j] = dp[-1][j-1]:表示单词1是空,单词2不是空的情况下,单词2要与单词1相同所需的最小删除步数,所以初始化为j
而其它元素可初始化为0;
关键点4:遍历顺序
由于下一个dp值与上一个dp值有关,因此for循环从前往后遍历(0已经初始化,且为使递归公式的dp[i-1][j-1]有意义,i,j都从1开始遍历)。文章来源:https://www.toymoban.com/news/detail-418287.html
class Solution {
public int minDistance(String word1, String word2) {
// dp[i][j],使得以i-1为结尾word1 和 以j-1为结尾的word2 相同所需的最小步数。
int[][] dp = new int[word1.length()+1][word2.length()+1];
// 初始化
for(int i = 0;i <= word1.length();i++){
dp[i][0] = i;
}
for(int j = 0;j <= word2.length();j++){
dp[0][j] = j;
}
for(int i = 1;i <= word1.length();i++){
for(int j = 1;j <= word2.length();j++){
if(word1.charAt(i-1) == word2.charAt(j-1) ){
dp[i][j] = dp[i-1][j-1];
}else{
// 删除单词1的字母/删除单词2的字母/两个单词的字母都删除
dp[i][j] = Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);
}
}
}
return dp[word1.length()][word2.length()];
}
}
72. 编辑距离
关键点1:dp数组的含义
dp[i][j],使得以i-1为结尾word1 和 以j-1为结尾的word2 相同所需的最小步数;
关键点2:递归公式的推导
if(nums1[i-1] == nums2[j-1]),则i和j同时移动,所以为i-1,j-1;dp[i][j] = dp[i-1][j-1];由于不需要进行删除操作,所以不需要加1
如果不相等:则有三种情况
情况1(增):i往前退一步,j不退 (操作加1)//增加单词1的字母
情况2(删):i不退,j往前退一步(操作加1)// 删除单词2的字母
情况3(改):i,j都往前退一步(操作加1)// 将其中一个单词的字母换成和另外一个单词的字母一样
关键点3:dp数组初始化
需要对最左边那列和最上面那行进行初始化
dp[i][0] = dp[i-1][-1]:表示单词1不是空,单词2是空的情况下,单词1要与单词2相同所需的最小删除步数,所以初始化为i
dp[0][j] = dp[-1][j-1]:表示单词1是空,单词2不是空的情况下,单词2要与单词1相同所需的最小删除步数,所以初始化为j
而其它元素可初始化为0;
关键点4:遍历顺序
由于下一个dp值与上一个dp值有关,因此for循环从前往后遍历(0已经初始化,且为使递归公式的dp[i-1][j-1]有意义,i,j都从1开始遍历)。
class Solution {
public int minDistance(String word1, String word2) {
// dp[i][j],使得以i-1为结尾word1 和 以j-1为结尾的word2 相同所需的最小步数。
int[][] dp = new int[word1.length()+1][word2.length()+1];
// 初始化
for(int i = 0;i <= word1.length();i++){
dp[i][0] = i;
}
for(int j = 0;j <= word2.length();j++){
dp[0][j] = j;
}
for(int i = 1;i <= word1.length();i++){
for(int j = 1;j <= word2.length();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-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
}
}
}
return dp[word1.length()][word2.length()];
}
}
文章来源地址https://www.toymoban.com/news/detail-418287.html
到了这里,关于代码随想录打卡第56天|583. 两个字符串的删除操作;72. 编辑距离的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!