嗯這里更具體講一講葱峡，思路是怎么一步一步想的勾给。
最開(kāi)始的思路是用Trie來(lái)表示所有可能subseq.
遍歷string S缸濒，對(duì)Trie中每個(gè)節(jié)點(diǎn)新建葉節(jié)點(diǎn)。
提交后果然答案對(duì)了植榕，但是Memory Limit Exceed再沧。
轉(zhuǎn)念一想，沒(méi)必要存下所有節(jié)點(diǎn)内贮，只需要知道當(dāng)前節(jié)點(diǎn)的數(shù)量就好了产园。
Trie中一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)seq。
假設(shè)當(dāng)前有N個(gè)不同的seq夜郁，每個(gè)seq加上一個(gè)新的字母什燕，又是新的N個(gè)不同sequence了。
但新的seq中竞端，有一部分原來(lái)就有屎即。
比如新的字母是'a'，那么原來(lái)以'a'結(jié)尾的seq事富，每一個(gè)都會(huì)存在新的這N個(gè)seq中技俐。
到這里，解題思路就比較清楚了统台。
我們需要用一個(gè)數(shù)組int endsWith[26]雕擂，
endsWith[i]來(lái)表示以第i個(gè)字母結(jié)束的sequence數(shù)量。
最后修飾一下代碼細(xì)節(jié)贱勃。
- 數(shù)組全部初始化為0井赌。
- 正好按照題目要求，空string不計(jì)作subseq贵扰。
- 每次更新的時(shí)候仇穗，end[i] = sum(end) + 1。
加一的原因是戚绕，比如我們遇到新字母'a'纹坐，新的N個(gè)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)
這個(gè)方法比較簡(jiǎn)潔耘子，時(shí)間O(26N)，空間O(26)
可以看心情優(yōu)化的地方是球切，用一個(gè)變量保存當(dāng)前數(shù)組和拴还，避免重復(fù)計(jì)算。
時(shí)間優(yōu)化到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)
