Leetcode 940 Distinct Subsequences II

发表于 |

给定一个字符串 S，计算 S 的不同非空子序列的个数。
因为结果可能很大，所以返回答案模 10^9 + 7.

示例 1：
输入：”abc”
输出：7
解释：7 个不同的子序列分别是 “a”, “b”, “c”, “ab”, “ac”, “bc”, 以及 “abc”。
示例 2：
输入：”aba”
输出：6
解释：6 个不同的子序列分别是 “a”, “b”, “ab”, “ba”, “aa” 以及 “aba”。
示例 3：
输入：”aaa”
输出：3
解释：3 个不同的子序列分别是 “a”, “aa” 以及 “aaa”。

提示：

  1. S 只包含小写字母。
  2. 1 <= S.length <= 2000

题意分析：
又到了说这句话的时候。看到mod 1e9+7就要想到dp，这在我写的题解里面经常提到。

思路分析：
在我们知道要用dp的情况，如何去定义dp呢，首先看数据范围，看我们能定义几维的dp
len(s) <= 2000，看样子可以定义2维的，但是按照套路来定义dp[i][j]表示s[i:j+1]中不同子序列的个数，好像是行不通的，因为推不出递推关系式。

这个时候可以换个思路，我定义dp[i][c]表示以字符c结尾的长度为i的子序列的个数
那么我们来分析一下递推式：
dp[3]['a']表示长度为3的以’a’结尾的子序列的个数。
那么它是不是等于所有长度为2的以’abcd…xyz’结尾的序列之和。
所以有， dp[n][c] = sum(dp[n-1][k] for k in 'abcd...xyz')

我们所求的结果应该怎么用dp来表示呢？
既然求所有的不同子序列的个数，那么应该是包括：
以’a’结尾的长度为(1,2,3,..,n)的子序列的个数
以’b’结尾的长度为(1,2,3,..,n)的子序列的个数
…
以’z’结尾的长度为(1,2,3,..,n)的子序列的个数
也就是所有dp[i][j]的和

最后考虑初始化条件，显然长度为1的以c结尾的子序列个数必为1。
也就是dp[1][c] = 1 for c in S

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# TLE 85/109 passed， O(n^2) time, O(26n) space
class Solution(object):
    def distinctSubseqII(self, S):
        n = len(S)
        mod = 10**9+7
        dp = [[0]*26 for _ in range(n+1)]
        res = 0
        
        for i in range(n):
            for l in range(i+1,0,-1):
                dp[l][ord(S[i])-ord('a')] = sum(dp[l-1]) % mod
            dp[1][ord(S[i])-ord('a')] = 1
        
        for i in range(1,len(dp)):
            for j in range(26):
                res += dp[i][j]
                res %= mod
        return res

但是很可惜，如果用空间这样迭代，会cost大量时间，并且最后计算res又要将整个dp重新迭代一遍
当len(s) = 2000时，平方就到了4000000，然后还迭代这么多次，最后超时了。

当然，len(s)<2000可以用2维dp这个理论是没错的，这里就涉及到leetcode中判题的方法了
像codeforces这种，都是每一个例子单独算，然后取所有例子中运行时间最大的时间作为你这道题的最终运行时间。
而leetcode是把所有的test case一起运，总时间作为你的运行时间。即使上面这个方法过单个2000长度的case很轻松，但是case一多，就会超时，我们得想办法优化一下。(可惜，如果不优化成1维，按照我这个思路，我调了很久都没调出来ac的代码，但是discuss里面好像有人是n^2的代码通过的)

我们注意到每一维的计算只与上一维的结果有关，可以用到滚动数组，这样就可以优化成一维的了。

1
2
3
4
5
6
7
8
# 180ms
class Solution(object):
    def distinctSubseqII(self, S):
        dp = [0] * 26
        mod = 10**9+7
        for ss in S:
            dp[ord(ss)-ord('a')] = sum(dp) + 1
        return sum(dp) % mod