题目
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
示例 1：
输入：s = "abc", t = "ahbgdc" 输出：true
示例 2：
输入：s = "axc", t = "ahbgdc" 输出：false
解题
方法一：动态规划
其实这道题和leetcode-1143：最长公共子序列依然是一样的。
如果s和t的最长公共子序列长度，等于s长度的本身，那么s就为t 的子序列
由于本题的s的特殊性：s即想要的子序列
可以将dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
换成dp[i][j]=dp[i][j-1]; 让长度为j-1的序列t来和s比，从而来减少复杂度,
没必要和i-1长度的s去比，因为s就是要求的子序列,如果去比i-1长度的s，肯定要比长度为i的s少的
class Solution { public: bool isSubsequence(string s, string t) { vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+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]+1; } else{ // dp[i][j]=max(dp[i-1][j],dp[i][j-1]); dp[i][j]=dp[i][j-1]; } } } return dp[s.size()][t.size()]==s.size(); } };
