代码随想录算法训练营第五十七天| 392.判断子序列、115.不同的子序列

代码随想录算法训练营第五十七天| 392.判断子序列、115.不同的子序列

---

文章目录

• 代码随想录算法训练营第五十七天| 392.判断子序列、115.不同的子序列
• • @[toc]
  • 392.判断子序列
  • • • 暴力遍历：
      • 动态规划：
  • 115.不同的子序列

392.判断子序列

题目链接：392. 判断子序列 - 力扣（LeetCode）

题目描述：

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

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

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

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

示例 2：

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

提示：

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

暴力遍历：

class Solution {
public:
    bool isSubsequence(std::string s, std::string t) {
        if(s.size()>t.size()) return 0;
        int sp = 0,tp = 0;
        while(sp<s.size() && tp<t.size()){
            if(t[tp] == s[sp]) sp++;
            tp++;
        }
        return sp==s.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

动态规划：

class Solution {
public:
    bool isSubsequence(std::string s, std::string t) {
        std::vector<std::vector<int>> dp(s.size()+1,std::vector<int> (t.size()+1));
        // dp[i][k] 表示 t 中前i个字母包含 s中前 k个字符 的个数
        for(int i = 1;i<=s.size();i++){
            for(int k = i;k<=t.size();k++){
                if(s[i-1] == t[k-1]){// 该位置字符相同
                    dp[i][k] = dp[i-1][k-1]+1;
                }else{// 不相同
                    dp[i][k] = dp[i][k-1];
                }
            }
        }
        return dp[s.size()][t.size()]==s.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

115.不同的子序列

题目链接：115. 不同的子序列 - 力扣（LeetCode）

题目描述：

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

示例 1：

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

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag
1
2
3
4
5
6
7
8
9

提示：

• 1 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

class Solution {
public:
    int numDistinct(std::string s, std::string t) {
        std::vector<std::vector<int>> dp(t.size()+1,std::vector<int> (s.size()+1,0));
        for(int i = 0;i<s.size();i++){
            dp[0][i] = 1;   
        }
        for(int i = 1;i<=t.size();i++){
            for(int  k = 1;k<=s.size();k++){
                if(t[i-1] == s[k-1]){
                    dp[i][k] = (dp[i-1][k-1] + dp[i][k-1])%(1000000007);
                }else{
                    dp[i][k] = dp[i][k-1];
                }
            }
        }
        return dp[t.size()][s.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---