392.判断子序列

题目

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

代码

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

115.不同的子序列

题目

115.不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

题目数据保证答案符合 32 位带符号整数范围。

示例 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

代码

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