嗯这里更具体讲一讲，思路是怎么一步一步想的。
最开始的思路是用Trie来表示所有可能subseq.
遍历string S，对Trie中每个节点新建叶节点。
提交后果然答案对了，但是Memory Limit Exceed。
转念一想，没必要存下所有节点，只需要知道当前节点的数量就好了。
Trie中一个节点对应一个seq。
假设当前有N个不同的seq，每个seq加上一个新的字母，又是新的N个不同sequence了。
但新的seq中，有一部分原来就有。
比如新的字母是'a'，那么原来以'a'结尾的seq，每一个都会存在新的这N个seq中。
到这里，解题思路就比较清楚了。
我们需要用一个数组int endsWith[26]，
endsWith[i]来表示以第i个字母结束的sequence数量。
最后修饰一下代码细节。
- 数组全部初始化为0。
- 正好按照题目要求，空string不计作subseq。
- 每次更新的时候，end[i] = sum(end) + 1。
加一的原因是，比如我们遇到新字母'a'，新的N个seq里不包含“a”，需要额外加上。
C++:
int distinctSubseqII(string S) {
long endsWith[26] = {}, mod = 1e9 + 7;
for (char c : S)
endsWith[c - 'a'] = accumulate(begin(endsWith), end(endsWith), 1L) % mod;
return accumulate(begin(endsWith), end(endsWith), 0L) % mod;
}
Java:
public int distinctSubseqII(String S) {
long end[] = new long[26], mod = (long)1e9 + 7;
for (char c : S.toCharArray())
end[c - 'a'] = Arrays.stream(end).sum() % mod + 1;
return (int)(Arrays.stream(end).sum() % mod);
}
Python:
def distinctSubseqII(self, S):
end = [0] * 26
for c in S:
end[ord(c) - ord('a')] = sum(end) + 1
return sum(end) % (10**9 + 7)
这个方法比较简洁，时间O(26N)，空间O(26)
可以看心情优化的地方是，用一个变量保存当前数组和，避免重复计算。
时间优化到O(N).
C++:
int distinctSubseqII2(string S) {
int res = 0, added = 0, mod = 1e9 + 7, endsWith[26] = {};
for (char c : S) {
added = (res - endsWith[c - 'a'] + 1) % mod;
res = (res + added) % mod;
endsWith[c - 'a'] = (endsWith[c - 'a'] + added) % mod;
}
return (res + mod) % mod;
}
Java:
public int distinctSubseqII2(String S) {
int end[] = new int[26], res = 0, added = 0, mod = (int)1e9 + 7;
for (char c : S.toCharArray()) {
added = (res + 1 - end[c - 'a']) % mod;
res = (res + added) % mod;
end[c - 'a'] = (end[c - 'a'] + added) % mod;
}
return (res + mod) % mod;
}
Python:
def distinctSubseqII(self, S):
res, end = 0, collections.Counter()
for c in S:
res, end[c] = res * 2 + 1 - end[c], res + 1
return res % (10**9 + 7)
