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 true
    int 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，第一行初始化为0
    for(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) {
        vectoruint64_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.思路一

• dp数组含义：以下标i-1结尾的word1，j-1结尾的word2，使它们相等的最小步数为dp[i][j]

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];
    //free
    for(int i = 0;i <= len1;i++){
        free(dp[i]);
    }
    free(dp);
    return result;
}