392 判斷子序列

題目鏈接：392. 判斷子序列 - 力扣（LeetCode）

給定字符串?s?和?t?，判斷?s?是否為?t?的子序列。

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

進階：

如果有大量輸入的 S，稱作 S1, S2, … , Sk 其中 k >= 10億，你需要依次檢查它們是否為 T 的子序列。在這種情況下，你會怎樣改變代碼？

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

思路：本題可使用雙指針分別遍歷s、t來進行判斷，這里不使用該方法，使用動態規劃方法獲取s和t的最長公共子序列長度，判斷是否與s的長度一致。

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;}
};

115 不同的子序列

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

給你兩個字符串?s?和?t?，統計并返回在?s?的?子序列?中?t?出現的個數，結果需要對?109?+ 7 取模。

輸入：s = "rabbbit", t = "rabbit"
輸出：3

思路：本題可看作是背包問題，從s中拿出字符，放到大小為t.size()的背包，放的條件是字符相等可放入，使用01背包模板。

class Solution {
public:int numDistinct(string s, string t) {int m = s.size(), n = t.size();const int mod = 1000000007;vector<int> dp(n + 1, 0);dp[0] = 1;for (int i = 0; i < m; i++) { // 遍歷物品for (int j = n; j >= 1; j--) { // 遍歷背包if(s[i] == t[j - 1]){dp[j] += dp[j - 1];dp[j] %= mod;}}}return dp[n];}
};