forked from liuyubobobo/Play-Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmain.cpp
67 lines (50 loc) · 1.33 KB
/
main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/// Source : https://leetcode.com/problems/distinct-subsequences-ii/
/// Author : liuyubobobo
/// Time : 2018-11-12
#include <iostream>
#include <vector>
using namespace std;
/// Dynamic Programming
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
private:
int MOD = 1e9 + 7;
public:
int distinctSubseqII(string S) {
int n = S.size();
vector<int> dp(n + 1, 1), last(26, -1);
dp[0] = 1;
for(int i = 0; i < n; i ++){
dp[i + 1] = 2 * dp[i] % MOD;
if(last[S[i] - 'a'] != -1){
dp[i + 1] -= dp[last[S[i] - 'a']];
if(dp[i + 1] < 0)
dp[i + 1] += MOD;
}
last[S[i] - 'a'] = i;
}
return dp[n] - 1 < 0 ? MOD - 1 : dp[n] - 1;
}
};
int main() {
string s1 = "abc";
cout << Solution().distinctSubseqII(s1) << endl;
// 7
string s2 = "aba";
cout << Solution().distinctSubseqII(s2) << endl;
// 6
string s3 = "aaa";
cout << Solution().distinctSubseqII(s3) << endl;
// 3
string s4 = "cdce";
cout << Solution().distinctSubseqII(s4) << endl;
// 13
string s5 = "lee";
cout << Solution().distinctSubseqII(s5) << endl;
// 5
string s6 = "bcbbca";
cout << Solution().distinctSubseqII(s6) << endl;
// 35
return 0;
}