LeetCode|动态规划|392. 判断子序列、115. 不同的子序列、 583. 两个字符串的删除操作

目录

一、392. 判断子序列

1.题目描述

2.解题思路

3.代码实现(双指针解法)

4.代码实现（动态规划解法）

二、115. 不同的子序列

1.题目描述

2.解题思路

3.代码实现（C语言版本）

4.代码实现（C++版本） 

三、583. 两个字符串的删除操作

 1.题目描述

2.解题思路

3.代码实现（C语言版本）

---

 

一、392. 判断子序列

1.题目描述

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

2.解题思路

1.双指针解法：这也是看到这个题目一开始想到的方法

• 指针p1指向s开头，指针p2指向t开头，分别判断是否相等，相等就p1++,p2++,否则就p2++ 

2.动态规划解法：判断这两个字符串数组，最长公共子序列长度是否==s.szie()

3.代码实现(双指针解法)

bool isSubsequence(char* s, char* t) {char* p1 = s;char* p2 = t;for(;*p1!='\0',*p2!='\0';){if(*p1==*p2){p1++;p2++;}else {p2++;}}if(*p1 == '\0')return true;return false;
}

4.代码实现（动态规划解法）

bool isSubsequence(char* s, char* t) {//考虑用最长公共子序列求解//动态规划思路，如果最长公共子序列的长度是字符串s的长度，那么就return trueint slen = strlen(s);int tlen = strlen(t);//对于dp数组初始化int **dp = (int**)malloc(sizeof(int*)*(slen+1));for(int i = 0;i <= slen;i++){dp[i] = (int*)malloc(sizeof(int) * (tlen+1));for(int j = 0;j <= tlen;j++){dp[i][j] = 0;}}for(int i = 1;i <= slen;i++){for(int j = 1;j<=tlen;j++){if(s[i-1]==t[j-1]){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = dp[i][j-1];}}}int result = dp[slen][tlen];for(int i = 0;i <= slen;i++){free(dp[i]);}free(dp);if(result == slen)  return true;else    return false;
}

二、115. 不同的子序列

1.题目描述

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

2.解题思路

• 动态规划解法，dp数组含义：以i-1结尾的s中，含有以j-1结尾的t的个数为dp[i][j]

3.代码实现（C语言版本）

int numDistinct(char* s, char* t) {int slen = strlen(s);int tlen = strlen(t);//dp数组含义：以i-1结尾的s中 有 以j-1结尾的t 的个数为dp[i][j]uint64_t** dp = (uint64_t**)malloc(sizeof(uint64_t*) * (slen+1));for(int i = 0; i <= slen;i++){dp[i] = (uint64_t*)malloc(sizeof(uint64_t)* (tlen+1));}//dp初始化:第一列初始化为1，第一行初始化为0for(int j = 1;j <= tlen;j++){dp[0][j] = 0;}for(int i = 0;i <= slen;i++){dp[i][0] = 1;}for(int i = 1;i <= slen;i++){for(int j = 1;j <= tlen;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];}}}uint64_t result = dp[slen][tlen];//打印dp数组for(int i = 0;i <= slen;i++){for(int j = 0;j <= tlen;j++){printf("%d ",dp[i][j]);}}for(int i = 0;i < slen;i++){free(dp[i]);}free(dp);return result;}

4.代码实现（C++版本） 

class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));for (int i = 0; i < s.size(); i++) dp[i][0] = 1;for (int j = 1; j < t.size(); j++) dp[0][j] = 0;for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); 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];}}}return dp[s.size()][t.size()];}
};

三、583. 两个字符串的删除操作

 1.题目描述

给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例  2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

• 1 <= word1.length, word2.length <= 500
• word1 和 word2 只包含小写英文字母

2.解题思路

1. 动态规划思路
2. 最长公共子序列思路：求出最长公共子序列长度，然后计算这两个字符串长度之和，减去2倍的最长公共子序列，就是我们要求的答案。

3.代码实现（C语言版本）

 

//min函数
int min(int a,int b){return a>b?b:a;
}int minDistance(char* word1, char* word2) {int len1 = strlen(word1);int len2 = strlen(word2);//dp数组含义：以下标i-1结尾的word1，j-1结尾的word2，使它们相等最小步数为dp[i][j]//初始化二维数组dp,第一行和第一列需要单独初始化，分别表是word1为空，word2以下标j结尾此时移动多少步相等，显然是j步int** dp = (int**)malloc(sizeof(int*)*(len1+1));for(int i = 0;i <= len1;i++){dp[i] = (int*)malloc(sizeof(int) * (len2+1));for(int j = 0;j <= len2;j++){dp[i][j] = 0;}}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[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));}}}int result = dp[len1][len2];//freefor(int i = 0;i <= len1;i++){free(dp[i]);}free(dp);return result;
}