搭建网站大概需要多少钱,网站做下载页面,内蒙古呼和浩特特产,网站建设所需素材文章目录 Day56两个字符串的删除操作题目思路代码 编辑距离题目思路代码 Day56
两个字符串的删除操作
583. 两个字符串的删除操作 - 力扣#xff08;LeetCode#xff09;
题目
给定两个单词 word1 和 word2#xff0c;找到使得 word1 和 word2 相同所需的最小步数#… 文章目录 Day56两个字符串的删除操作题目思路代码 编辑距离题目思路代码 Day56
两个字符串的删除操作
583. 两个字符串的删除操作 - 力扣LeetCode
题目
给定两个单词 word1 和 word2找到使得 word1 和 word2 相同所需的最小步数每步可以删除任意一个字符串中的一个字符。
示例
输入: “sea”, “eat”输出: 2解释: 第一步将sea变为ea第二步将eat变为ea
思路
本题和动态规划115.不同的子序列 (opens new window)相比其实就是两个字符串都可以删除了情况虽说复杂一些但整体思路是不变的。
这次是两个字符串可以相互删了这种题目也知道用动态规划的思路来解
动规五部曲
确定dp数组dp table以及下标的含义
dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。
确定递推公式 当word1[i - 1] 与 word2[j - 1]相同的时候当word1[i - 1] 与 word2[j - 1]不相同的时候
当word1[i - 1] 与 word2[j - 1]相同的时候dp[i][j] dp[i - 1][j - 1];
当word1[i - 1] 与 word2[j - 1]不相同的时候有三种情况
情况一删word1[i - 1]最少操作次数为dp[i - 1][j] 1
情况二删word2[j - 1]最少操作次数为dp[i][j - 1] 1
情况三同时删word1[i - 1]和word2[j - 1]操作的最少次数为dp[i - 1][j - 1] 2
那最后当然是取最小值所以当word1[i - 1] 与 word2[j - 1]不相同的时候递推公式dp[i][j] min({dp[i - 1][j - 1] 2, dp[i - 1][j] 1, dp[i][j - 1] 1});
因为 dp[i][j - 1] 1 dp[i - 1][j - 1] 2所以递推公式可简化为dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1);
这里可能不少录友有点迷糊从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1]dp[i][j-1] 本来就不考虑 word2[j - 1]了那么我在删 word1[i - 1]是不是就达到两个元素都删除的效果即 dp[i][j-1] 1。
dp数组如何初始化
从递推公式中可以看出来dp[i][0] 和 dp[0][j]是一定要初始化的。
dp[i][0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。 for(int i 1; i len1 1; i) dp[i][0] i;for(int j 1; j len2 1; j) dp[0][j] j;dp[0][0] 0;确定遍历顺序
从递推公式 dp[i][j] min(dp[i - 1][j - 1] 2, min(dp[i - 1][j], dp[i][j - 1]) 1); 和dp[i][j] dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。
所以遍历的时候一定是从上到下从左到右这样保证dp[i][j]可以根据之前计算出来的数值进行计算。
举例推导dp数组
代码
class Solution {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;dp[0][0] 0;for(int i 1; i len1 1; i){for(int j 1; j len2 1; j){if(word1.charAt(i - 1) word2.charAt(j - 1)){dp[i][j] dp[i - 1][j - 1];}else{dp[i][j] Math.min(dp[i - 1][j - 1] 2, Math.min(dp[i][j - 1], dp[i - 1][j]) 1);}}}return dp[len1][len2];}
}编辑距离
72. 编辑距离 - 力扣LeetCode
题目
给你两个单词 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 500word1 和 word2 由小写英文字母组成
思路
编辑距离是用动规来解决的经典题目这道题目看上去好像很复杂但用动规可以很巧妙的算出最少编辑距离。
动规五部曲
确定dp数组dp table以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。
确定递推公式
在确定递推公式的时候首先要考虑清楚编辑的几种操作整理如下
if (word1[i - 1] word2[j - 1])不操作
if (word1[i - 1] ! word2[j - 1])增删换在整个动规的过程中最为关键就是正确理解dp[i][j]的定义
if (word1[i - 1] word2[j - 1]) 那么说明不用任何编辑dp[i][j] 就应该是 dp[i - 1][j - 1]即dp[i][j] dp[i - 1][j - 1];
if (word1[i - 1] ! word2[j - 1])此时就需要编辑了如何编辑呢
操作一word1删除一个元素那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] dp[i - 1][j] 1;
操作二word2删除一个元素那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] dp[i][j - 1] 1;
这里有同学发现了怎么都是删除元素添加元素去哪了。
word2添加一个元素相当于word1删除一个元素例如 word1 ad word2 aword1删除元素d 和 word2添加一个元素d变成word1a, word2ad 最终的操作数是一样
操作三替换元素word1替换word1[i - 1]使其与word2[j - 1]相同此时不用增删加元素。
可以回顾一下if (word1[i - 1] word2[j - 1])的时候我们的操作 是 dp[i][j] dp[i - 1][j - 1] 对吧。
那么只需要一次替换的操作就可以让 word1[i - 1] 和 word2[j - 1] 相同。
所以 dp[i][j] dp[i - 1][j - 1] 1;
综上当 if (word1[i - 1] ! word2[j - 1]) 时取最小的即dp[i][j] min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) 1;
if(word1.charAt(i - 1) word2.charAt(j - 1)){dp[i][j] dp[i - 1][j - 1];
}else{dp[i][j] Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) 1;
}dp数组如何初始化
dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。
那么dp[i][0] 和 dp[0][j] 表示什么呢
dp[i][0] 以下标i-1为结尾的字符串word1和空字符串word2最近编辑距离为dp[i][0]。
那么dp[i][0]就应该是i对word1里的元素全部做删除操作即dp[i][0] i;
同理dp[0][j] j;
dp[0][0] 0 空字符串和空字符串不需要操作就相等 for(int i 0; i word1.length() 1; i) dp[i][0] i;for(int j 0; j word2.length() 1; j) dp[0][j] j;dp[0][0] 0;确定遍历顺序
从如下四个递推公式
dp[i][j] dp[i - 1][j - 1]dp[i][j] dp[i - 1][j - 1] 1dp[i][j] dp[i][j - 1] 1dp[i][j] dp[i - 1][j] 1
可以看出dp[i][j]是依赖左方上方和左上方元素的如图
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nByVxeHF-1691224926511)(https://code-thinking-1253855093.file.myqcloud.com/pics/20210114162113131.jpg “72.编辑距离”)] for(int i 1; i word1.length() 1; i){for(int j 1; j word2.length() 1; j){if(word1.charAt(i - 1) word2.charAt(j - 1)){dp[i][j] dp[i - 1][j - 1];}else{dp[i][j] Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) 1;}}}举例推导dp数组
代码
class Solution {public int minDistance(String word1, String word2) {// dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。int dp[][] new int[word1.length() 1][word2.length() 1];for(int i 0; i word1.length() 1; i) dp[i][0] i;for(int j 0; j word2.length() 1; j) dp[0][j] j;dp[0][0] 0;for(int i 1; i word1.length() 1; i){for(int j 1; j word2.length() 1; j){if(word1.charAt(i - 1) word2.charAt(j - 1)){dp[i][j] dp[i - 1][j - 1];}else{// 操作一word1删除一个元素那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。 dp[i - 1][j] 1;// 操作二word2删除一个元素那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。 dp[i][j - 1] 1// 操作三替换元素word1替换word1[i - 1]使其与word2[j - 1]相同此时不用增删加元素。 dp[i - 1][j - 1] 1dp[i][j] Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) 1;}}}return dp[word1.length()][word2.length()];}
}
