# 940. Distinct Subsequences II 不同的子序列 II

@TOC

## # 题目描述

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:

1. S contains only lowercase letters.
2. 1 <= S.length <= 2000

## # 解题方法

### # 动态规划

``````Input: "aba"
Current parsed: "ab"

endswith 'a': ["a"]
endswith 'b': ["ab","b"]

"a" -> "aa"
"ab" -> "aba"
"b" -> "ba"
"" -> "a"

endswith 'a': ["aa","aba","ba","a"]
endswith 'b': ["ab","b"]
result: 6
``````

``````class Solution(object):
def distinctSubseqII(self, S):
"""
:type S: str
:rtype: int
"""
nums = [0] * 26
for s in S:
nums[ord(s) - ord("a")] = (sum(nums) + 1) % (10 ** 9 + 7)
return sum(nums) % (10 ** 9 + 7)
``````

## # 日期

2018 年 11 月 11 日 —— 剁手节快乐