392.判断子序列 

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

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

进阶：

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

致谢：

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

解题思路：

确认dp含义：dp[i][j]以i-1 和j-1结尾的数组相同字符数最大数量

递推公式：当s[i-1] == t[j-1]，dp[i][j] = dp[i-1][j-1]+1，else 将t倒退前一位得到dp[i][j-1]，这里因为t比s大，在t中判断是否有s，因此s不用倒退一个

初始化：dp[i][0] = 0, dp[0][j] = 0

遍历顺序：从前到后

打印dp数组

class Solution:def isSubsequence(self, s: str, t: str) -> bool:dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]res = 0for i in range(1, len(s)+1):for j in range(1, len(t)+1):if s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1]+1else:dp[i][j] = dp[i][j-1]res = max(res, dp[i][j])return res==len(s)

class Solution:def numDistinct(self, s: str, t: str) -> int:dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]for i in range(len(s)+1):dp[i][0] = 1dp[0][0] = 1for i in range(1, len(s)+1):for j in range(1, len(t)+1):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[len(s)][len(t)]