目录

0115:不同的子序列(★★)

力扣第 115 题

题目

给你两个字符串 s t ,统计并返回在 s子序列t 出现的个数,结果需要对 109 + 7 取模。

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

提示:

  • 1 <= s.length, t.length <= 1000
  • st 由英文字母组成

相似问题:

分析

#1

典型的 dp,按是否由 s[-1] 拼成 t[-1] 即可递推。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        mod = 10**9+7
        m,n = len(s),len(t)
        dp = [[1]+[0]*n for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(n+1):
                dp[i][j] = dp[i-1][j]
                if j and s[i-1]==t[j-1]:
                    dp[i][j] += dp[i-1][j-1]
                    dp[i][j] %= mod
        return dp[-1][-1]

401 ms

#2

可以将 dp 优化为一维数组。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        mod = 10**9+7
        m,n = len(s),len(t)
        dp = [1]+[0]*n 
        for i in range(1,m+1):
            for j in range(n,0,-1):
                if s[i-1]==t[j-1]:
                    dp[j] += dp[j-1]
                    dp[j] %= mod
        return dp[-1]

263 ms