什么网站动物和人做的,重庆专业网站搭建,宁波网站推广设计,开一家代做网站的公司LeetCode 583- 两个字符串的删除操作
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
题目描述#xff1a;给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字…LeetCode 583- 两个字符串的删除操作
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
解题思路
确定dp数组dp table以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t最少删除dp[i][j]个元素可以得到相同的字符串。
确定递推公式
首先分两种情况当前字符相等和不相等若相等则直接dp[i][j] dp[i-1][j-1]表示我们不用执行任何操作。
若不相等则需要分三种情况 首先是删除第一个字符串中的字符也就是dp[i-1][j]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,dp[i-1][j-1]2});
dp数组如何初始化
dp[i][0] 表示以下标i-1为结尾的字符串和空串相等所需要操作的最少步数故应该是i故dp[i][0]i dp[0][j]同理。
确定遍历顺序
依据递推公式我们可以看出dp[i][j]是由左边和左上的以及上面的状态推出的所以我们从上至下从左向右遍历即可。
举例推导dp数组
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size() 1, vectorint(word2.size() 1));for (int i 0; i word1.size(); i) dp[i][0] i;for (int j 0; j word2.size(); j) dp[0][j] j;for (int i 1; i word1.size(); i) {for (int j 1; j word2.size(); j) {if (word1[i - 1] word2[j - 1]) {dp[i][j] dp[i - 1][j - 1];} else {dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1);}}}return dp[word1.size()][word2.size()];}
};总结
这题可以省略dp[i-1][j-1]2这种情况因为这种情况我们已经在别的情况里讨论到了也就是dp[i-1][j]1是删除idp[i][j-1]是删除j两个各执行一次就包含了这种情况了。
LeetCode 72- 编辑距离
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符
解题思路
1.确定dp数组dp table以及下标的含义
dp[i][j]代表字符串1以i-1下标为结尾的部分和字符串2以j-1为结尾的部分转换所需要的最小操作数。
2.确定递推公式
我们需要分情况讨论首先字符串1与字符串2当前字符相等或不等的情况
相等则不进行操作。也就是dp[i][j] dp[i-1][j-1]不相等时又有三种操作删除第一个字符串中的字符删除第二个字符串中的字符或修改其中一个字符这样就可以使得这两个字符在下标范围内通过这些操作可以成相同的了。故我们又取最小值故dp[i][j] min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]}) 1
这里我们不用考虑插入元素为什么呢因为插入就相当于是添加元素如果我们删除第一个字符串的一个字符就等同于给第二个字符串添加一个元素。
3.dp数组如何初始化
首先dp[i][0]代表的是第一个字符串从i-1下标开始第二个字符串为空串时操作最少步骤使得两个字符串相等。故我们全部只需要删除即可也就是i步即可。dp[0][j]同理。
4.确定遍历顺序
依据递推公式我们可以看出dp[i][j]是由左边和左上的以及上面的状态推出的所以我们从上至下从左向右遍历即可。
5.举例推导dp数组
class Solution {
public:int minDistance(string word1, string word2) {int len1 word1.size();int len2 word2.size();vectorvectorint dp(len11,vectorint(len21,0));for(int j0;jlen2;j)dp[0][j] j;for(int i0;ilen1;i)dp[i][0] i;for(int i1;ilen1;i){for(int j1;jlen2;j){if(word1[i-1] word2[j-1]){dp[i][j] dp[i-1][j-1];}else{dp[i][j] min({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]})1;}}}return dp[len1][len2];}
};
总结
本题关键还是要理解dp数组的含义要将其牢记在心这样才能真正弄懂一道题。这题主要难点就是对于两个字符串进行操作的时候的情况讨论。
