-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDistinctSubsequencesII.js
More file actions
43 lines (38 loc) · 1.2 KB
/
Copy pathDistinctSubsequencesII.js
File metadata and controls
43 lines (38 loc) · 1.2 KB
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
// https://leetcode-cn.com/problems/distinct-subsequences-ii/
var Test = require('../Common/Test');
var distinctSubseqII = function (s) {
const mod = 1000000007;
// const dp = Array(s.length + 1).fill(0);
// dp[0] = 1;
const dp = [1]
const lastOccurs = new Map();
for (let i = 0; i < s.length; i++) {
const char = s[i];
dp[i + 1] = (dp[i] * 2 - (lastOccurs.has(char) ? dp[lastOccurs.get(char)] : 0)) % mod;
lastOccurs.set(char, i);
}
return (dp[s.length] + mod) % mod - 1;
};
function test(s) {
Test.test(distinctSubseqII, s);
}
// test("abc");
// test("aba");
// test("aab");
// test("abaa");
// test("aaba");
// test("aa");
// test("aaa");
// test("aaaa");
// test("zchmliaqdgvwncfatcfivphddpzjkgyygueikthqzyeeiebczqbqhdytkoawkehkbizdmcnilcjjlpoeoqqoqpswtqdpvszfaksn");
test("blljuffdyfrkqtwfyfztpdiyktrhftgtabxxoibcclbjvirnqyynkyaqlxgyybkgyzvcahmytjdqqtctirnxfjpktxmjkojlvvrr");
// "abc"
// "aba"
// "aab"
// "abaa"
// "aaba"
// "aa"
// "aaa"
// "aaaa"
// "zchmliaqdgvwncfatcfivphddpzjkgyygueikthqzyeeiebczqbqhdytkoawkehkbizdmcnilcjjlpoeoqqoqpswtqdpvszfaksn"
// "blljuffdyfrkqtwfyfztpdiyktrhftgtabxxoibcclbjvirnqyynkyaqlxgyybkgyzvcahmytjdqqtctirnxfjpktxmjkojlvvrr"