0115：不同的子序列（★★）

2015-04-25 约 302 字预计阅读 1 分钟次阅读

力扣第 115 题

题目

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10⁹ + 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
s 和 t 由英文字母组成

分析

#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

目录

0115：不同的子序列（★★）

题目

分析

#1

#2

解答