简单做网站,做国外百科知识网站,怎样制作一个购物小程序,推广软文平台题目1#xff1a;583 两个字符串的删除操作
题目链接#xff1a;两个字符串的删除操作
对题目的理解
返回使两个单词word1和word2相同的最少删除多少个元素#xff0c;两个单词至少包含一个字母#xff0c;且仅包含小写字母
思路1#xff1a;这道题与昨天的不同子序列…题目1583 两个字符串的删除操作
题目链接两个字符串的删除操作
对题目的理解
返回使两个单词word1和word2相同的最少删除多少个元素两个单词至少包含一个字母且仅包含小写字母
思路1这道题与昨天的不同子序列很相似只是有一点不同不同子序列是使用s字符串去匹配t字符串而本题可以对word1进行删减得到word2也可以用word2删减获得word1经过一系列删除操作最终两个单词相等就可以了。
思路2本题其实就是求word1和word2达到最长公共子序列时使用两个单词的长度之和减去最长公共子序列的长度的2倍。
动态规划思路1
动规五部曲
1dp数组及下标i的含义
dp[i][j]以i-1结尾的word1和以j-1结尾的word2达到word1和word2相同的最少操作次数
2递推公式
还是考虑两种情况当前子串word1结尾的字符与子串word2结尾的字符相等和不等的情况
i结尾的字符相等即word1[i-1]word2[j-1]因为已经相等了这两个字符就不会改变操作的次数那么此时就不用考虑这两个字符了模拟将这两个字符删除则当前的结果与这两个字符的前面的字符结尾(word1[i-1],word2[j-1])的结果相同即dp[i][j] dp[i-1][j-1]
ii结尾的字符不等因为word1[i-1]和word2[j-1]两个字符不等所以考虑删除元素这又可以分为3种情况 删除word1[i-1] 也就是不考虑word1[i-1]这个元素了那么在word1中没有这个元素了则最终的结果应该是其前一个字符word1[i-2]与word2[j-1]进行比较看是否相等
即 dp[i][j]dp[i-1][j]1因为删除一个元素所以加1
删除word2[j-1] 不考虑word2[j-1]这个元素了那么在word2中就没有这个元素了则最终的结果应该是word2子串的前一个字符word2[j-2]与word1[i-1]进行比较看是否相等
即dp[i][j]dp[i][j-1]因为删除了一个元素所以加1
删除word1[i-1]和word2[j-1]不考虑word1[i-1]和word2[j-1]这两个元素了那么在word1和word2中就没有这两个元素了最终就是word2子串的前一个字符word2[i-2]与word1子串的前一个字符word1[i-2]进行比较 即 dp[i][j]dp[i-1][j-1]2因为删除了2个元素所以加2
dp[i][j] min(dp[i-1][j]1,dp[i][j-1]1,dp[i-1][j-1]2)
3dp数组初始化 根据递推公式第一行第一列都要进行初始化即dp[i][0] dp[0][j]都需要进行初始化
根据dp数组定义 dp[i][0]代表以i-1结尾的word1和以-1结尾的word2相同的最小操作次数word2以-1结尾说明word2是空串那么要想达到两个子串相等说明word1需要删除i个元素需要最少操作i次所以dp[i][0]i
同理dp[0][j]代表以-1结尾的word1和以j-1结尾的word2相同的最小操作次数word1是空串此时要想让两个子串相等word1也需要变为空串需要将word2中的元素全部删除才可以即删除j个元素最少操作j次 所以dp[0][j]j
4遍历顺序
根据递推公式从左到右遍历从上到下遍历 5打印dp数组
代码注意定义dp数组的时候一定要word1.size()1一定要加1因为dp数组的定义是以i-1结尾最终要遍历到最后一个元素word1.size()-1的时候才是dp数组的最后一个元素word1.size()减去1为结尾
class Solution {
public:int minDistance(string word1, string word2) {//定义dp数组vectorvectorint dp(word1.size()1,vectorint(word2.size()1));//初始化dp数组for(int i0;iword1.size();i) dp[i][0]i;for(int j0;jword2.size();j) dp[0][j]j;for(int i1;iword1.size();i){for(int j1;jword2.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,min(dp[i][j-1]1,dp[i-1][j-1]2));}}return dp[word1.size()][word2.size()];}
};
上面的代码会出现如下错误 根据出现的错误将其对应的各个dp数组打印出来发现dp[0][1]以及dp[1][0]仍是0并没有初始化成1所以初始化这里出现了问题 就是因为在初始化的时候没有将dp[word1.size()][0]和dp[0][word2.size()]初始化
注意初始化数组时因为是初始化整个dp[i][j]所以将dp[i][0]和dp[0][j]整个进行初始化所以i从0到word1.size()都要初始化 j从0到word2.size()都要初始化注意初始化时一定要使得iword1.size()jword2.size()等号不能丢掉否则就会在案例出现的时候出现错误
因此将代码修改如下
class Solution {
public:int minDistance(string word1, string word2) {//定义dp数组vectorvectorint dp(word1.size()1,vectorint(word2.size()1));//初始化dp数组for(int i0;iword1.size();i) dp[i][0]i;for(int j0;jword2.size();j) dp[0][j]j;for(int i1;iword1.size();i){for(int j1;jword2.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,min(dp[i][j-1]1,dp[i-1][j-1]2));}}return dp[word1.size()][word2.size()];}
};
时间复杂度: O(n * m)空间复杂度: O(n * m)
流程图 动态规划思路2
思路2本题也可以在求最长公共子序列的基础上进行求解将word1和word2的最长公共子序列的长度求出来然后使用word1和word2的长度之和减去2倍的公共子序列的长度即为所求。
流程 代码
class Solution {
public:int minDistance(string word1, string word2) {//定义并初始化dp数组vectorvectorint dp(word1.size()1,vectorint(word2.size()1,0));for(int i1;iword1.size();i){for(int j1;jword2.size();j){if(word1[i-1]word2[j-1]) dp[i][j]dp[i-1][j-1]1;else dp[i][j]max(dp[i-1][j],dp[i][j-1]); }}int result word1.size()word2.size()-2*dp[word1.size()][word2.size()];return result;}
};
时间复杂度: O(n * m)空间复杂度: O(n * m)
题目272 编辑距离
题目链接编辑距离
对题目的理解
返回将单词word1转换成word2使用最少的操作数两个单词的长度大于等于0且均由小写字母组成操作包括插入一个字符删除一个字符以及替换一个字符
动态规划
动规五部曲
1dp数组及下标i的定义
dp[i][j]以下标i-1结尾的word1和以下标j-1结尾的word2相同的最少操作次数
2递推公式
还是分为两种情况两个元素相等以及两个元素不等的情况
1两个元素word1[i-1]和word2[j-1]相等则不考虑这两个元素因为已经相等了所以不需要对二者进行操作只需要考虑前面的word1[i-2]和word2[j-2]就行dp[i][j]dp[i-1][j-1]
2两个元素word1[i-1]和word2[j-1]不相等则需要对元素进行删减以及替换的操作所以这又可以分为3种情况
i只考虑word1[i-1]只对这个元素进行操作当word1[i-1]不等于word2[j-1]时将word1[i-1]删除那么此时对于word1而言就是以word1[i-2]为结尾的子串与word2[j-1]为结尾的子串的最小操作次数的基础上进行操作删除加1因此dp[i][j]dp[i-1][j]1 加1是因为进行了一个删除操作
ii只考虑word2[j-1]只对这个元素进行操作当word1[i-1]不等于word2[j-1]时将word2[j-1]删除那么对于word2而言只剩下以word2[j-2]为结尾的子串与word1[i-1]为结尾的子串的最小操作次数的基础上进行操作删除加1dp[i][j]dp[i][j-1]1 加1是因为进行了一个删除操作
注word2添加一个元素相当于word1删除一个元素例如 word1 ad word2 aword1删除元素d 和 word2添加一个元素d变成word1a, word2ad 最终的操作数是一样
iii如果word1[i-1]不等于word2[j-1]要使得这两个位置对应的元素相等dp[i][j]dp[i-1][j-1]这个等式是word[i-1]和word[j-1]相等的情况但是此时是要让这两个元素相等所以需要考虑这两个元素在原来以word1[i-2]为结尾的子串和以word2[j-2]为结尾的子串相同进行操作的基础上加上一个替换的操作就ok只需要dp[i][j]dp[i-1][j-1]1 加1是因为进行了一次替换操作
dp[i][j] min(dp[i-1][j]1,dp[i][j-1]1,dp[i-1][j-1]1)
3dp数组初始化
根据递推公式第一行和第一列需要初始化
根据dp数组的定义dp[i][0]表示以下标i-1为结尾的word1和以下标-1为结尾的word2相同的最少操作次数而以下标-1为结尾的word2是一个空串要想使得这两个串的长度相等那么word1至少需要操作i次因为word1中含有i个元素
dp[0][j]表示以下标-1为结尾的word1和以下标j-1为结尾的word2相同的最少操作次数而以下标01结尾的word1是一个空串要想使得word1和word2的长度相等那么word2至少需要操作j次因为word2中含有j个元素
因此初始化如下 注意for循环中一定要是小于等于一定要有等于这样才能确保dp数组中的最后一个边界值即dp[word1.size()][0]和dp[0][word2.size()]初始化了如果只写小于的话这组元素就会被落掉相当于dp[word1.size()][0]和dp[0][word2.size()]没有进行初始化默认为0
4遍历顺序
根据递推公式从左往右遍历从上到下遍历 5打印dp数组
最终的结果在dp[word1.size()][word2.size()]中
代码
class Solution {
public:int minDistance(string word1, string word2) {//定义dp数组vectorvectorint dp(word1.size()1,vectorint(word2.size()1));//初始化dp数组for(int i0;iword1.size();i) dp[i][0]i;for(int j0;jword2.size();j) dp[0][j]j;for(int i1;iword1.size();i){for(int j1;jword2.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,min(dp[i][j-1]1,dp[i-1][j-1]1));}}return dp[word1.size()][word2.size()];}
};
时间复杂度: O(n * m)空间复杂度: O(n * m)
代码流程
删减元素 添加元素
