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

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

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

进阶：

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

致谢：

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

• 示例 1：

  输入：s = “abc”, t = “ahbgdc”
  输出：true

• 示例 2：

  输入：s = “axc”, t = “ahbgdc”
  输出：false

提示：

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

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] = dp[i][j - 1];}}if (dp[s.size()][t.size()] == s.size()) return true;return false;}
};

给你两个字符串 s 和 t，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 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

提示：

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

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()];}
};