难度: Hard
原题连接
内容描述
Given a string S, count the number of distinct, non-empty subsequences of S .
Since the result may be large, return the answer modulo 10^9 + 7.
Example 1:
Input: "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".
Example 2:
Input: "aba"
Output: 6
Explanation: The 6 distinct subsequences are "a", "b", "ab", "ba", "aa" and "aba".
Example 3:
Input: "aaa"
Output: 3
Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".
Note:
S contains only lowercase letters.
1 <= S.length <= 2000
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******
DP
dp[i]代表以S[i-1]为结尾的distinct subsequence的个数
dp[0] = 1，因为一个字符都没有只能是空字符串
如果当前字符s[i-1]之前没有出现过，那么自然我们的d[i] = 2 * dp[i-1]
我们可以用字典存一下之前出现过的字符
beats 100%
class Solution:
def distinctSubseqII(self, S):
"""
:type S: str
:rtype: int
"""
lookup = {}
dp = [0] * (len(S)+1)
dp[0] = 1
for i in range(1, len(S)+1):
dp[i] = 2 * dp[i-1]
if S[i-1] in lookup:
dp[i] = dp[i] - dp[lookup[S[i-1]]]
lookup[S[i-1]] = i-1
return (dp[-1]-1) % (10**9 + 7)思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******
endWith某个字符的思路，见lee215
假设当前有N个不同的seq，每个seq加上一个新的字母，又是新的N个不同sequence了。
但新的seq中，有一部分原来就有。
比如新的字母是'a'，那么原来以'a'结尾的seq，每一个都会存在新的这N个seq中。
到这里，解题思路就比较清楚了。
我们需要用一个数组int endsWith[26]，
endsWith[i]来表示以第i个字母结束的sequence数量。
最后修饰一下代码细节。
数组全部初始化为0。
正好按照题目要求，空string不计作subseq。
每次更新的时候，end[i] = sum(end) + 1。
加1的原因是，比如我们遇到新字母'a'，新的N个seq里不包含“a”本身这种情况，需要额外加上。
class Solution:
def distinctSubseqII(self, S):
"""
:type S: str
:rtype: int
"""
end = [0] * 26
for c in S:
end[ord(c) - ord('a')] = sum(end) + 1
return sum(end) % (10**9 + 7)还可以用一个变量保存当前数组和，避免重复计算。
class Solution:
def distinctSubseqII(self, S):
"""
:type S: str
:rtype: int
"""
res, end = 0, {}
for c in S:
res, end[c] = res * 2 + 1 - end.get(c, 0), res + 1
return res % (10**9 + 7)