Problem
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
Solution: DP
counts[i][j] := # of distinct sub sequences of s[1->i] and ends with letter j. (‘a'<= j <= ‘z’)
Initialization:
counts[*][*] = 0
Transition:
counts[i][j] = sum(counts[i-1]) + 1 if s[i] == j else counts[i-1][j]
ans = sum(counts[n])
e.g. S = “abc”
counts[1] = {‘a’ : 1}
counts[2] = {‘a’ : 1, ‘b’ : 1 + 1 = 2}
counts[3] = {‘a’ : 1, ‘b’ : 2, ‘c’: 1 + 2 + 1 = 4}
ans = sum(counts[3]) = 1 + 2 + 4 = 7
Time complexity: O(N*26)
Space complexity: O(N*26) -> O(26)
C++
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua, running time: 12 ms class Solution { public: int distinctSubseqII(string S) { constexpr int kMod = 1e9 + 7; std::vector<int> counts(26); for (char c : S) counts[c - 'a'] = accumulate(begin(counts), end(counts), 1L) % kMod; return accumulate(begin(counts), end(counts), 0L) % kMod; } }; |
Python3
1 2 3 4 5 6 7 8 |
# Author: Huahua, running time: 64 ms class Solution: def distinctSubseqII(self, S): kMod = 10**9 + 7 dp = {} for c in S: dp[c] = (sum(dp.values()) + 1) % kMod return sum(dp.values()) % kMod |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment