网站建设过程和准备阶段,建设征婚网站,淘宝服务商平台,平面设计大师583.两个字符串的删除操作
力扣题目链接/文章讲解
视频讲解
1、确定 dp 数组下标及值含义
dp[i][j]#xff1a;以下标 i 为结尾的字符串 word1#xff0c;和以下标 j 为结尾的字符串 word2#xff0c;想要达到相等#xff0c;所需要删除元素的最少次数为 dp[i][j]
2、…583.两个字符串的删除操作
力扣题目链接/文章讲解
视频讲解
1、确定 dp 数组下标及值含义
dp[i][j]以下标 i 为结尾的字符串 word1和以下标 j 为结尾的字符串 word2想要达到相等所需要删除元素的最少次数为 dp[i][j]
2、确定递推公式
当 word1[i] word2[j] 时
这个时候只需要考虑怎么对 word1[0, i - 1] 和 word2[0, j - 1] 删除到相同即可
即 dp[i][j] dp[i - 1][j - 1]
当 word1[i] ! word2[j] 时
可以先删除 word1[i]然后再对 word1[0, i - 1] 和 word2[0, j] 删除到相同
即 dp[i - 1][j] 1其中 1 表示“先删除 word1[i]”dp[i - 1][j] 是对 word1[0, i - 1] 和 word2[0, j] 删除到相同所需要的最少次数
可以先删除 word2[j]然后再对 word1[0, i] 和 word2[0, j - 1] 删除到相同
即 dp[i][j - 1] 1其中 1 表示“先删除 word2[j]”dp[i][j - 1] 是对 word1[0, i] 和 word2[0, j - 1] 删除到相同所需要的最少次数
因为求最少这两种删除的方式所需要删除元素的最少次数取最小即为 dp 值
即 dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1)
始终别忘了我们 dp 数组的值是删除元素的最少次数
3、dp 数组初始化
需要初始化 dp[i][0] 和 dp[0][j]
dp[i][0]以 i 为结尾的字符串 word1和 word2[0] 想要达到相等所需要删除元素的最少次数
dp[0][j]以 j 为结尾的字符串 word2和 word1[0] 想要达到相等所需要删除元素的最少次数
我们发现到这里很难初始化
怎么办呢用我们之前的思路更改 dp[i][j] 的定义重新来一遍
1、确定 dp 数组下标及值含义
dp[i][j]以下标 i - 1 为结尾的字符串 word1和以下标 j - 1 为结尾的字符串 word2想要达到相等所需要删除元素的最少次数为 dp[i][j]
2、确定递推公式
还是按照我们之前的思路
当 word1[i - 1] word2[j - 1] 时
这个时候只需要考虑怎么对 word1[0, i - 2] 和 word2[0, j - 2] 删除到相同即可
即 dp[i][j] dp[i - 1][j - 1]
当 word1[i - 1] ! word2[j - 1] 时
可以先删除 word1[i - 1]然后再对 word1[0, i - 2] 和 word2[0, j - 1] 删除到相同
即 dp[i - 1][j] 1
可以先删除 word2[j]然后再对 word1[0, i] 和 word2[0, j - 1] 删除到相同
即 dp[i][j - 1] 1
因为求最少这两种删除的方式所需要删除元素的最少次数取最小即为 dp 值
即 dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1)
始终别忘了我们 dp 数组的值是删除元素的最少次数
3、dp 数组初始化
需要初始化 dp[i][0] 和 dp[0][j]
dp[i][0]以下标 i - 1 为结尾的字符串 word1和空字符串想要达到相等所需要删除元素的最少次数即将 word1 中的 i 个字符下标 0 到下标 i - 1 总共有 i 个字符全删了dp[i][0] i
dp[0][j]以下标 j - 1 为结尾的字符串 word2和空字符串想要达到相等所需要删除元素的最少次数即将 word2 中的 j 个字符全删了dp[0][j] j
4、确定遍历顺序从上向下从左往右遍历填充 dp 数组
5、打印 dp 数组验证
代码如下
class Solution {
public:int minDistance(string word1, string word2) {// dp[i][j]以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2想要达到相等所需要删除元素的最少次数为dp[i][j]dp下标最大值-1要能达到字符串的结尾故dp维度要比word维度多1vectorvectorint dp(word1.size() 1, vectorint(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]; // 直接考虑该怎么对word1[i-2]和word2[j-2]做删除操作}else {dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1);// 先删除一个再考虑怎么对剩下的做删除操作}}}return dp[word1.size()][word2.size()];}
};
本题我们真真切切体验到了哪怕思路相同不同定义 dp 的方式带来的代码难度也会不同
另一种思路只要求出两个字符串的最长公共子序列长度即可那么除了最长公共子序列之外的字符都是必须删除的最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size() 1, vectorint(word2.size() 1, 0));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] 1;elsedp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}}return word1.size() word2.size() - 2 * dp[word1.size()][word2.size()];}
};
72.编辑距离
力扣题目链接/文章讲解
视频讲解
上一道题只能删除操作这道题可以插入、删除、替换
1、确定 dp 数组下标及值含义
dp[i][j]以下标 i - 1 为结尾的字符串 word1和以下标 j - 1 为结尾的字符串 word2想要达到相等所需要的最少操作次数为 dp[i][j]
这里为什么定义以下标-1为结尾上一道题目体验过了就是为了方便初始化
2、确定递推公式
考虑怎么让以下标 i - 1 为结尾的字符串 word1和以下标 j - 1 为结尾的字符串 word2 变得相同必然涉及到比较元素
当 word1[i - 1] word2[j - 1] 时
这个时候只需要考虑怎么对 word1[0, i - 2] 和 word2[0, j - 2] 操作到相同即可
即 dp[i][j] dp[i - 1][j - 1] 当 word1[i - 1] ! word2[j - 1] 时
这部分是难点
考虑下一步可以执行三种操作
删除操作
可以先删除 word1[i - 1]然后再对 word1[0, i - 2] 和 word2[0, j - 1] 操作到相同此时最少操作数为 dp[i - 1][j] 11 代表先执行的删除操作dp[i - 1][j] 为对 word1[0, i - 2] 和 word2[0, j - 1] 操作到相同所需要的最少操作数可以先删除 word2[j - 1]然后再对 word1[0, i - 1] 和 word2[0, j - 1] 操作到相同此时最少操作数为 dp[i][j - 1] 1
插入操作插入操作的次数和删除操作的次数是一样的互为逆向操作。word2添加一个元素相当于word1删除一个元素
我们还是推导一下来证明插入和删除操作的次数是一样的。可以先在 word1[0, i - 1] 末尾加一个 word2[i - 1]然后再对 word1[0, i - 1] 和 word2[0, j - 2] 操作到相同。此时最少操作数为 dp[i][j - 1] 1即删除操作中的第二种情况。 如果先在 word2[0, j - 1] 末尾加一个 word1[i - 1]然后再对 word1[0, i - 2] 和 word2[0, j - 1] 操作到相同则对应删除操作中的第一种情况为 dp[i - 1][j] 1
替换操作
先将 word1[i - 1] 或 word2[j - 1] 替换为相同元素然后再对 word1[0, i - 2] 和 word2[0, j - 2] 操作到相同。此时最少操作数为 dp[i - 1][j - 1] 11 代表先执行的替换操作dp[i - 1][j - 1] 为对 word1[0, i - 2] 和 word2[0, j - 2] 操作到相同所需要的最少操作数
综上所述当 word1[i - 1] ! word2[j - 1] 时取上述每种操作所有情况的最小值
dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1, dp[i - 1][j - 1] 1)
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;
}
3、dp 数组初始化 需要初始化第一行和第一列
再回顾一下dp[i][j]的定义
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[0, i - 1] 里的元素全部做删除操作即dp[i][0] i
同理dp[0][j] j
4、确定遍历顺序
dp[i][j] 是依赖左方上方和左上方元素需要从左到右从上到下去遍历填充
5、打印 dp 数组验证
代码如下
class Solution {
public:int minDistance(string word1, string word2) {// 定义dp数组注意dp数组的大小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]) // 直接对word1[0,i-2]和word2[0,j-2]操作dp[i][j] dp[i - 1][j - 1];else {// 先删除或添加再对剩下的操作、先替换再对剩下的操作dp[i][j] min({dp[i - 1][j] 1, dp[i][j - 1] 1, dp[i - 1][j - 1] 1});}}}return dp[word1.size()][word2.size()];}
}; 回顾总结
编辑距离问题结束
总结一下最近的题目都是操作两个字符串定义 dp 数组和确定递推公式都挺难的
确定递推公式时一般需要考虑比较元素相等或不相等两种情况
动态规划分解为子问题的思想需要贯穿先执行了某个操作后后续操作是否可以由其他 dp 值推导而来
