网站 前端,上海市建设厅网站查询,软件开发app制作公司排名,建设专业网站网络代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结 文章链接#xff1a;两个字符串的删除操作、编辑距离、编辑距离总结 视频链接#xff1a;两个字符串的删除操作、编辑距离 1. LeetCode 583. 两个字符串的删除操作
1.1 思…代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结 文章链接两个字符串的删除操作、编辑距离、编辑距离总结 视频链接两个字符串的删除操作、编辑距离 1. LeetCode 583. 两个字符串的删除操作
1.1 思路
题目给我们两个字符串问两个字符串最少可以删除多少个元素使这两个字符串相同。本题相对于115. 不同的子序列难在于两个都可以删dp 数组及其下标的含义比较两个字符串里的每个元素是否相同的情况就定义二维数组dp[i][j]以 i-1 为结尾的 word1 和以 j-1 为结尾的 word2为了让它们相同的最少操作次数为 dp[i][j]。定义 i-1 和 j-1 是为了方便初始化递推公式ifword1[i-1]word2[j-1]dp[i][j]dp[i-1][j-1] 因为这两个元素已经相同了考虑与不考虑都是一样的因此直接继承dp[i-1][j-1]因为两个元素都相同了就可以不操作它们了。else 就是word1[i-1]!word2[j-1] 的情况就需要删除元素了如果删除word1[i-1]dp[i][j]dp[i-1][j]1 这里就是模拟出了删除 word1[i-1]如果删除word2[j-1]dp[i][j]dp[i][j-1]1 这里就是模拟出了删除 word2[j-1]如果都删了就是 dp[i][j]dp[i-1][j-1]2。因此如果两个元素不相同就是 dp[i][j]Math.min三个取最小值 dp 数组的初始化根据递推公式得到推导方向因此第一行和列都需要初始化dp[0][j] 表示以-1 为结尾即空字符串 word1要想和 word2 相同的最小操作次数就应该是 j因为 word2 就需要删掉 j 个元素dp[i][0] 表示以-1 为结尾即空字符串 word2要想和 word1 相同的最小操作次数就应该是 1因为 word1 就需要删掉 i 个元素。其余下标因为会被覆盖因此默认即可遍历顺序从推导方向可以看出就是从左到右从上到下 forint i1iword1.length()iforint j1word2t.length()j为什么从 1 开始为什么要等于号以前解释过了。最终结果保存在 dp[word1.length()][word2.length()]打印 dp 数组用于 debug其实本题也可以通过求1143. 最长公共子序列一样求出最长公共子序列然后两个原字符串总和相加减去 2 倍的最长公共子序列的长度就是要求的最小操作次数
1.2 代码
// dp数组中存储需要删除的字符个数
class Solution {public int minDistance(String word1, String word2) {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;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] 2,Math.min(dp[i - 1][j] 1, dp[i][j - 1] 1));}}}return dp[word1.length()][word2.length()];}
}
//DP - longest common subsequence (用最長公共子序列反推)
class Solution {public int minDistance(String word1, String word2) {char[] char1 word1.toCharArray();char[] char2 word2.toCharArray();int len1 char1.length;int len2 char2.length;int dp[][] new int [len1 1][len2 1];for(int i 1; i len1; i){for(int j 1; j len2; j){if(char1[i - 1] char2[j - 1])dp[i][j] dp[i - 1][j - 1] 1;elsedp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}}return len1 len2 - (2 * dp[len1][len2]);//和leetcode 1143只差在這一行。}
}2. LeetCode 72. 编辑距离
2.1 思路
本题是给我们两个字符串如何让 word1 和 word2 相等可以通过添加、删除、替换元素对 word1 和 word2 操作都可以增加 word1 的元素也就是相当于删除 word2 的元素因此操作方式很多样dp 数组及其下标的含义比较两个字符串的相同情况我们要定义一个二维数组dp[i][j]以 i-1 为结尾的 word1 和以 j-1 为结尾的 word2 最少操作次数为 dp[i][j] 能使两个字符串相等。为什么以 i-1 和 j-1 结尾是为了方便初始化递推公式要求相同就要比较每个元素讨论它们相同与不相同的情况 ifword1[i-1]word2[j-1]dp[i][j]dp[i-1][j-1] 因为两个元素都相同了就可以不改变操作次数不需要任何操作。else 就是两个元素不相同有增加、删除、替换等操作如果删掉 word1 的第 i-1 个元素那就是 dp[i][j]dp[i-1][j]1也就是以 i-2 为结尾和以 j-1 为结尾的相同的最小操作数的基础上1如果删掉 word2 的第 j-1 个元素dp[i][j]dp[i][j-1]1如果两个元素不相同选择替换元素无论是替换 word1 的还是 word2 的把其中一个的替换成另一个的就可以了因此是 dp[i][j]dp[i-1][j-1]1这里含义是把 word1 的第 i-1 个元素换成了 word2 的第 j-1 个元素或者 word2 的第 j-1 个元素换成了 word1 的第 i-1 个元素。因此 dp[i][j]Math.min三者取最小值。为什么这里没有添加元素的操作呢因为对 word1 添加其实就相当于对 word2 删除反之也是同理因此我们用删除代替了添加效果是一样的 dp 数组的初始化根据递推公式得到推导方向因此我们要初始化第一行和列都初始化了dp[i][0]也就是以 i-1 为结尾的字符串 word1 和以-1 为结尾的空字符串 word2word1 要最少操作 i 次才能与 word2 相等因此 forint i0iword1.length()idp[i][0]idp[0][j]以-1 为结尾的空字符串 word1 和以 j-1 为结尾的字符串 word2word2 最少操作 j 次才能与 word1 相等因此 forint j0jword2.length()jdp[0][j]j。为什么取等于号因为 dp是以 i-1 为结尾和 j-1 为结尾的一定要取等了才能表示最后一个元素为结尾。其余下标无所谓会被覆盖默认为 0 即可。遍历顺序根据递推公式和推导方向就一定是从左到右和从上到下forint i1iword1.length()iforint j1word2t.length()j为什么从 1 开始为什么取等于号上面解释过了。最终结果保存在 dp[word1.length()][word2.length()]打印 dp 数组用于 debug
2.2 代码
public int minDistance(String word1, String word2) {int m word1.length();int n word2.length();int[][] dp new int[m 1][n 1];// 初始化for (int i 1; i m; i) {dp[i][0] i;}for (int j 1; j n; j) {dp[0][j] j;}for (int i 1; i m; i) {for (int j 1; j n; j) {// 因为dp数组有效位从1开始// 所以当前遍历到的字符串的位置为i-1 | j-1if (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]), dp[i - 1][j]) 1;}}}return dp[m][n];
}3. 编辑距离总结
本题是通过三道题铺垫而来的
3.1 392. 判断子序列
给定字符串 s 和 t 判断 s 是否为 t 的子序列。 这道题目 其实是可以用双指针或者贪心的的但是我在开篇的时候就说了这是编辑距离的入门题目因为从题意中我们也可以发现只需要计算删除的情况不用考虑增加和替换的情况。
if (s[i - 1] t[j - 1]) t中找到了一个字符在s中也出现了 if (s[i - 1] ! t[j - 1]) 相当于t要删除元素继续匹配 状态转移方程
if (s[i - 1] t[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;
else dp[i][j] dp[i][j - 1];3.2 115. 不同的子序列
给定一个字符串 s 和一个字符串 t 计算在 s 的子序列中 t 出现的个数。
本题虽然也只有删除操作不用考虑替换增加之类的但相对于392. 判断子序列就有难度了这道题目双指针法可就做不了。
当s[i - 1] 与 t[j - 1]相等时dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配那么个数为dp[i - 1][j - 1]。
一部分是不用s[i - 1]来匹配个数为dp[i - 1][j]。
这里可能有同学不明白了为什么还要考虑 不用s[i - 1]来匹配都相同了指定要匹配啊。
例如 sbagg 和 tbag s[3] 和 t[2]是相同的但是字符串s也可以不用s[3]来匹配即用s[0]s[1]s[2]组成的bag。
当然也可以用s[3]来匹配即s[0]s[1]s[3]组成的bag。
所以当s[i - 1] 与 t[j - 1]相等时dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];
当s[i - 1] 与 t[j - 1]不相等时dp[i][j]只有一部分组成不用s[i - 1]来匹配即dp[i - 1][j]
所以递推公式为dp[i][j] dp[i - 1][j];
状态转移方程
if (s[i - 1] t[j - 1]) {dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];
} else {dp[i][j] dp[i - 1][j];
}3.3 583. 两个字符串的删除操作
给定两个单词 word1 和 word2找到使得 word1 和 word2 相同所需的最少步数每步可以删除任意一个字符串中的一个字符。
本题和115. 不同的子序列相比其实就是两个字符串可以都可以删除了情况虽说复杂一些但整体思路是不变的。
当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});
状态转移方程
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] 2, dp[i - 1][j] 1, dp[i][j - 1] 1});
}3.4 72. 编辑距离
给你两个单词 word1 和 word2请你计算出将 word1 转换成 word2 所使用的最少操作数 。
编辑距离终于来了有了前面三道题目的铺垫应该有思路了本题是两个字符串可以增删改比392. 判断子序列、115. 不同的子序列、583. 两个字符串的删除操作要复杂很多
在确定递推公式的时候首先要考虑清楚编辑的几种操作整理如下
if (word1[i - 1] word2[j - 1]) 不操作 if (word1[i - 1] ! word2[j - 1]) 增删换
也就是如上四种情况。
if (word1[i - 1] word2[j - 1]) 那么说明不用任何编辑dp[i][j] 就应该是 dp[i - 1][j - 1]即dp[i][j] dp[i - 1][j - 1];
此时可能有同学有点不明白为啥要即dp[i][j] dp[i - 1][j - 1]呢
那么就在回顾上面讲过的dp[i][j]的定义word1[i - 1] 与 word2[j - 1]相等了那么就不用编辑了以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1] 就是 dp[i][j]了。
在下面的讲解中如果哪里看不懂就回想一下dp[i][j]的定义就明白了。
在整个动规的过程中最为关键就是正确理解dp[i][j]的定义
if (word1[i - 1] ! word2[j - 1])此时就需要编辑了如何编辑呢
操作一word1增加一个元素使其word1[i - 1]与word2[j - 1]相同那么就是以下标i-2为结尾的word1 与 i-1为结尾的word2的最近编辑距离 加上一个增加元素的操作。 即 dp[i][j] dp[i - 1][j] 1;
操作二word2添加一个元素使其word1[i - 1]与word2[j - 1]相同那么就是以下标i-1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个增加元素的操作。 即 dp[i][j] dp[i][j - 1] 1;
这里有同学发现了怎么都是添加元素删除元素去哪了。
word2添加一个元素相当于word1删除一个元素例如 word1 “ad” word2 “a”word2添加一个元素d也就是相当于word1删除一个元素d操作数是一样
操作三替换元素word1替换word1[i - 1]使其与word2[j - 1]相同此时不用增加元素那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。 即 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[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;
}
