判断子序列（LeetCode-392）
题目
给定字符串 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
两个字符串都只由小写字符组成。
思路
和最长公共子序列（LeetCode-1143）类似
五部曲
dp[i][j] 含义
长度为 [ 0 , i − 1 ] 的字符串s与长度为 [ 0 , j − 1 ] 的字符串t的相同子序列长度
递推公式
如果 s [ i − 1 ] = t [ j − 1 ]
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1
如果二者不相等，沿用之前结果
d p [ i ] [ j ] = d p [ i ] [ j − 1 ]
数组初始化
dp[i][0] 与空串一起求最长公共子序列，自然为零
遍历顺序
从前往后
测试用例
代码展示
class Solution { public: bool isSubsequence(string s, string t) { int n1 = s.size(); int n2 = t.size(); vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1)); for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; 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]; } } } return (dp[n1][n2] == n1 ? true : false); } };
我直接修改最长公共子序列（LeetCode-1143）的代码做的结果，实际上就是看最长公共子序列长度是否为s字符串长度，如果相等，即s为t的子序列
class Solution { public: bool isSubsequence(string s, string t) { int n1 = s.size(); int n2 = t.size(); vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1)); for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (s[i - 1] == t[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } } } return (dp[n1][n2] == n1 ? true : false); } };
