-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDistinctSubsequencesII.V2.js
More file actions
44 lines (39 loc) · 1.28 KB
/
Copy pathDistinctSubsequencesII.V2.js
File metadata and controls
44 lines (39 loc) · 1.28 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
44
// 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);
const lastOccurs = Array(26).fill();
dp[0] = 1;
for (let i = 0; i < s.length; i++) {
const char = s[i];
const charIndex = char.charCodeAt(0)-97;
const lastOccur = lastOccurs[charIndex];
dp[i + 1] = (dp[i] * 2 - (lastOccur == undefined ? 0 : dp[lastOccur] )) % mod;
lastOccurs[charIndex] = 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"