当前位置：首页 > news >正文

代码随想录算法训练营第45天|LeetCode 115.不同的子序列、583. 两个字符串的删除操作、72. 编辑距离

news 来源：原创 2024/9/21 16:17:54

1.LeetCode 115.不同的子序列

题目链接：https://leetcode.cn/problems/distinct-subsequences/
文章链接：https://programmercarl.com/0115.不同的子序列.html
视频链接：https://www.bilibili.com/video/BV1fG4y1m75Q/

在这里插入图片描述

思路：
1.确定dp数组（dp table）以及下标的含义
dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
2.确定递推公式
两种情况：

s[i - 1] 与 t[j - 1]相等
- 用s[i - 1]来匹配：个数为dp[i - 1][j - 1]。即，不需要考虑当前s子串和t子串的最后一位字母，只考虑s子串中0至i-2下标内的字母是否与子串t中0至i-2下标内的子串是否匹配。
- 不用s[i - 1]来匹配：个数为dp[i - 1][j]。即，不需要考虑当前s子串的最后一位字母，只考虑s子串中0至i-2下标内的字母是否与子串t是否匹配。
  此时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
s[i - 1] 与 t[j - 1] 不相等
此时，dp[i][j] = dp[i - 1][j];

3.dp数组如何初始化
dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。即，dp[i][0]一定都是1；
dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。即，dp[0][j]一定都是0；
dp[0][0]应该是1。
注意：当i或j为0时，子串是空字符串。
每次当初始化的时候，都要回顾一下dp[i][j]的定义，不要凭感觉初始化。
4.确定遍历顺序
从上到下，从左到右
5.返回值
dp数组最后一个元素。
dp[length1][length2]。

解法：
class Solution {public int numDistinct(String s, String t) {//1.定义dp数组//dp[i][j]：表示以i-1结尾s子串中出现以j-1结尾t子串的个数int[][] dp = new int[s.length()+1][t.length()+1];//2.递推公式/**if (s.charAt(i-1) == t.charAt(j-1)) {dp[i][j] = dp[i-1][j-1] + dp[i-1][j];} else {dp[i][j] = dp[i-1][j];}*///3.初始化for (int i=0;i<s.length()+1;i++) {dp[i][0] = 1;} //4.遍历顺序for (int i=1;i<s.length()+1;i++) {for (int j=1;j<t.length()+1;j++) {if (s.charAt(i-1) == t.charAt(j-1)) {dp[i][j] = dp[i-1][j-1] + dp[i-1][j];} else {dp[i][j] = dp[i-1][j];}}}return dp[s.length()][t.length()];}
}

2. LeetCode 583. 两个字符串的删除操作

题目链接：https://leetcode.cn/problems/delete-operation-for-two-strings/
文章链接：https://programmercarl.com/0583.两个字符串的删除操作.html#思路
视频链接：https://www.bilibili.com/video/BV1we4y157wB/

在这里插入图片描述

思路：
1.确定dp数组（dp table）以及下标的含义
dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
2.确定递推公式
当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);
3.dp数组如何初始化
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;
}
4.确定遍历顺序
从上到下，从左到右
5.返回值
dp数组最后一个元素

class Solution {public int minDistance(String word1, String word2) {//1.定义dp//dp[i][j] 表示以i-1结尾的序列与以j-1结尾的序列含有相同子序列的最小删除次数int[][] dp = new int[word1.length()+1][word2.length()+1];//2.递推公式/**if (word1.charAt(i) == word2.charAt(j)) {dp[i][j] = dp[i-1][j-1];} else {dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j-1]+1);}*///3.初始化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;}//4.遍历顺序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,dp[i][j-1]+1);}}}return dp[word1.length()][word2.length()];}
}

注意：本题也可以使用最长公共子序列的方法解决。因为本题最终获取的子序列就是最长的公共子序列。

3. LeetCode 72. 编辑距离

题目链接：https://leetcode.cn/problems/edit-distance/description/
文章链接：https://programmercarl.com/0072.编辑距离.html#思路
视频链接：https://www.bilibili.com/video/BV1qv4y1q78f/

在这里插入图片描述

1.确定dp数组（dp table）以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
或者：dp[i][j]表示以i-1结尾的序列转换成以j-1结尾的序列所使用的最少的操作数。
注意：题目是将word1转成word2，则只需要对word1进行操作。
2.确定递推公式
a.word1[i - 1] == word2[j - 1]：说明不用任何编辑，即：dp[i][j] = dp[i - 1][j - 1];
b.word1[i - 1] != word2[j - 1]：
i.word1删除一个元素。即：dp[i][j] = dp[i - 1][j] + 1;
ii.word1添加一个元素。而word1添加一个元素等价于word2删除一个元素。即：dp[i][j] = dp[i][j - 1] + 1;
iii.word1替换一个元素。即：dp[i][j] = dp[i - 1][j - 1] + 1;
综上：当 word1[i - 1] != word2[j - 1]时取最小的，即：dp[i][j] = Math.min(Math.min(dp[i][j - 1] + 1,dp[i - 1][j] + 1),dp[i - 1][j - 1] + 1);
3.dp数组如何初始化
dp[i][0]是对word1里的元素全部做删除操作，即：dp[i][0] = i;
dp[0][j]是对word1里的元素全部做插入操作，即：dp[0][j] = j;
注意：0代表是空字符串。
4.确定遍历顺序
从左到右从上到下去遍历。
5.返回值
dp数组最后一个元素。

class Solution {public int minDistance(String word1, String word2) {//1.定义dp数组//dp[i][j]表示以i-1结尾的序列转换成以j-1结尾的序列所使用的最少的操作数int[][] dp = new int[word1.length()+1][word2.length()+1];//2.递推公式/**if (word1.charAt(i-1) == word2.charAt(j-1)) {dp[i][j] = dp[i-1][j-1];} else {delete = dp[i-1][j]+1;transfer = dp[i-1][j-1]+1;insert = dp[i][j-1]+1;dp[i][j] = Math.min(insert,delete,transfer);}*///3.初始化// 删除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;} //4.遍历顺序int delete;int transfer;int insert;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 {delete = dp[i-1][j]+1;transfer = dp[i-1][j-1]+1;insert = dp[i][j-1]+1;dp[i][j] = Math.min(Math.min(insert,delete),transfer);}}}return dp[word1.length()][word2.length()];}
}