JLUVicent

392判断子序列&115不同的子序列

 
  • 2023年 04月10日
  • 0 阅读

day55

392.判断子序列

题目链接：392. 判断子序列

解题思路： 参考 视频

本题和最长公共子序列问题相同，最后就是判断最终的长度是否等于字符串s的长度

详细参考1143.最长公共子序列

class Solution {
public:
    bool isSubsequence(string s, string t) {
        // 动态规划
        vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,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] + 1;
                }else{
                    dp[i][j] = max( dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return (dp[s.size()][t.size()] == s.size());
    }
};

本题也可以直接用暴力方法解决，第一次写AC了，代码如下：

class Solution {
public:
    bool isSubsequence(string s, string t) {
        // 暴力模拟
        int tmp = -1;
        int count = 0;
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < t.size(); j++) {
                if (s[i] == t[j] && j > tmp) {
                    tmp = j;
                    count++;
                    break;
                }
            }
        }
        return (count == s.size());
    }
};

115.不同的子序列

题目链接：115. 不同的子序列

解题思路：参考 视频

#### 1.确定dp数组及下标含义

以i-1为结尾的s中有j-1为结尾的t的个数为$dp[i][j]$

2.确定递推公式

有两种方式来推导

  • s[i-1] == t[j-1]: $dp[i][j] = dp[i-1][j-1]+dp[i-1][j];$ 分为两部分，一个是通过s[i-1]来匹配，结果为$dp[i-1][j-1]$，另外一部分是不包含s[i-1]，个数为$dp[i-1][j]$; eg: bagg bag
  • s[i-1] != t[j-1]: $dp[i][j] = dp[i-1][j];$，不相等时候直接去前一个的情况作为当前状态即可。

3.初始化dp数组

$dp[i][0] = 1;$ 相当于t为空数组，此时相当于出现了1次

$dp[0][j]=0;$相当于s为空数组，此时相当于t在s中出现了0次

对于$dp[0][0] = 1;$

4.确定遍历顺序

从上到下，从左到右

5.打印dp数组

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1,0));//不这样写力扣测试用例会溢出 uint64_t
        for( int i = 0; i < s.size()+1; i++){
            dp[i][0] = 1;
        }
        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()];
    }
};
搜索