大连住房和建设局网站,网站的速度,漳州企业网站开发,那个网站做720度效果图583. 两个字符串的删除操作
思路
#动态规划一
本题和动态规划#xff1a;115.不同的子序列 (opens new window)相比#xff0c;其实就是两个字符串都可以删除了#xff0c;情况虽说复杂一些#xff0c;但整体思路是不变的。
这次是两个字符串可以相互删了#xff0c;这…583. 两个字符串的删除操作
思路
#动态规划一
本题和动态规划115.不同的子序列 (opens new window)相比其实就是两个字符串都可以删除了情况虽说复杂一些但整体思路是不变的。
这次是两个字符串可以相互删了这种题目也知道用动态规划的思路来解动规五部曲分析如下
确定dp数组dp table以及下标的含义
dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。
这里dp数组的定义有点点绕大家要撸清思路。
确定递推公式当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。
dp[0][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[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数组
以word1:seaword2:eat为例推导dp数组状态图如下 以上分析完毕代码如下
// 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()];}
}
时间复杂度: O(n * m)空间复杂度: O(n * m)
#动态规划二
本题和动态规划1143.最长公共子序列 (opens new window)基本相同只要求出两个字符串的最长公共子序列长度即可那么除了最长公共子序列之外的字符都是必须删除的最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。
代码如下
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 word1.length(); i) {for (int j 1; j word2.length(); j) {if (word1.charAt(i - 1) word2.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1] 1;} else {dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}}}int len dp[len1][len2];return len1 len2 - 2 * len;}
}
时间复杂度: O(n * m)空间复杂度: O(n * m) 72. 编辑距离
思路
编辑距离终于来了这道题目如果大家没有了解动态规划的话会感觉超级复杂。
编辑距离是用动规来解决的经典题目这道题目看上去好像很复杂但用动规可以很巧妙的算出最少编辑距离。
接下来依然使用动规五部曲对本题做一个详细的分析
#1. 确定dp数组dp table以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。
为啥要表示下标i-1为结尾的字符串呢为啥不表示下标i为结尾的字符串呢
为什么这么定义卡哥在 718. 最长重复子数组 (opens new window)中做了详细的讲解。
其实用i来表示也可以 用i-1就是为了方便后面dp数组初始化的。
#2. 确定递推公式
在确定递推公式的时候首先要考虑清楚编辑的几种操作整理如下
if (word1[i - 1] word2[j - 1])不操作
if (word1[i - 1] ! word2[j - 1])增删换也就是如上4种情况。
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删除一个元素那么就是以下标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 最终的操作数是一样 dp数组如下图所示意的 a a d---------- ---------------| 0 | 1 | | 0 | 1 | 2 |---------- ---------------a | 1 | 0 | a | 1 | 0 | 1 |---------- ---------------d | 2 | 1 |----------操作三替换元素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[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里的元素全部做删除操作即dp[i][0] i;
同理dp[0][j] j;
所以C代码如下
for (int i 0; i word1.size(); i) dp[i][0] i;
for (int j 0; j word2.size(); j) dp[0][j] j;#4. 确定遍历顺序
从如下四个递推公式
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]是依赖左方上方和左上方元素的如图 所以在dp矩阵中一定是从左到右从上到下去遍历。
代码如下
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 - 1][j], dp[i][j - 1]}) 1;}}
}#5. 举例推导dp数组
以示例1为例输入word1 horse, word2 ros为例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 0; i len1; i) dp[i][0]i;for (int j 0; j len2; j) dp[0][j]j;for (int i 1; i len1; i) {for (int j 1; j len2; 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], Math.min(dp[i][j - 1],dp[i-1][j-1]))1;}}}return dp[len1][len2];}
}
时间复杂度: O(n * m)空间复杂度: O(n * m)
