class Solution {
public:
int distinctSubseqII(string s) {
}
};
940. 不同的子序列 II
给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。
示例 1：
输入：s = "abc" 输出：7 解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
示例 2：
输入：s = "aba" 输出：6 解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
示例 3：
输入：s = "aaa" 输出：3 解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
提示：
1 <= s.length <= 2000s 仅由小写英文字母组成
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-10-09 09:48:34
const mod = 1e9 + 7
func distinctSubseqII(s string) int {
n := len(s)
dp := [26]int{} //以字符s[i]结尾时子序列数量
dp[s[0]-'a'] = 1
total := 1 //总子序列数量
for i := 1; i < n; i++ {
temp := dp[s[i]-'a'] //用一个临时变量保存一下将要更新的以s[i]结尾的子序列数量
dp[s[i]-'a'] = (total + 1) % mod
//以s[i]结尾的子序列更新为total+1,因为新加入了字符，可以与之前所有子序列匹配一次，因为新s[i]在老s[i]后面，老s[i]形成的子序列新s[i]肯定也有
total += (dp[s[i]-'a'] - temp) //新增了(dp[s[i]-'a'] - temp个子序列
}
return total%mod
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2 MB, 提交时间: 2023-10-09 09:48:11
const mod int64 = 1e9 + 7
const mod2 int = 1e9 + 7
func distinctSubseqII1(s string) int {
n := len(s)
f := make([][26]int, n)
f[0][s[0]-'a'] = 1
for i := 1; i < n; i++ {
total := int64(0)
for _, v := range f[i-1] {
total += int64(v)
}
f[i] = f[i-1]
f[i][s[i]-'a'] = 1 + int(total%mod)
}
total := int64(0)
for _, v := range f[n-1] {
total += int64(v)
}
return int(total % mod)
}
func distinctSubseqII2(s string) int {
f := [26]int{}
for _, c := range s {
total := int64(0)
for _, v := range f {
total += int64(v)
}
f[c-'a'] = 1 + int(total%mod)
}
total := int64(0)
for _, v := range f {
total += int64(v)
}
return int(total % mod)
}
func distinctSubseqII(s string) (total int) {
f := [26]int{}
for _, c := range s {
c -= 'a'
others := total - f[c] // total 中不含 f[c] 的部分（由于取模的原因，这里的减法可能会产生负数）
f[c] = 1 + total // 更新 f[c]
total = ((f[c]+others)%mod2 + mod2) % mod2 // 更新 total，并保证 total 非负
}
return
}
java 解法, 执行用时: 2 ms, 内存消耗: 39.7 MB, 提交时间: 2023-10-09 09:46:31
class Solution {
private final long MOD = (long) 1e9 + 7;
private final int MOD2 = (int) 1e9 + 7;
public int distinctSubseqII1(String s) {
var n = s.length();
var f = new long[n][26];
f[0][s.charAt(0) - 'a'] = 1;
for (var i = 1; i < n; i++) {
f[i] = f[i - 1].clone();
f[i][s.charAt(i) - 'a'] = (1 + Arrays.stream(f[i - 1]).sum()) % MOD;
}
return (int) (Arrays.stream(f[n - 1]).sum() % MOD);
}
public int distinctSubseqII2(String s) {
var f = new long[26];
var n = s.length();
for (var i = 0; i < n; i++)
f[s.charAt(i) - 'a'] = (1 + Arrays.stream(f).sum()) % MOD;
return (int) (Arrays.stream(f).sum() % MOD);
}
// 再优化
public int distinctSubseqII(String s) {
var total = 0;
var f = new int[26];
var n = s.length();
for (var i = 0; i < n; ++i) {
var c = s.charAt(i) - 'a';
var others = total - f[c]; // total 中不含 f[c] 的部分（由于取模的原因，这里的减法可能会产生负数）
f[c] = 1 + total; // 更新 f[c]
total = ((f[c] + others) % MOD2 + MOD2) % MOD2; // 更新 total，并保证 total 非负
}
return total;
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.7 MB, 提交时间: 2023-10-09 09:44:27
class Solution {
const int MOD = 1e9 + 7;
public:
int distinctSubseqII1(string s) {
int n = s.length();
vector<array<int, 26>> f(n);
f[0][s[0] - 'a'] = 1;
for (int i = 1; i < n; ++i) {
f[i] = f[i - 1];
f[i][s[i] - 'a'] = accumulate(f[i - 1].begin(), f[i - 1].end(), 1L) % MOD;
}
return accumulate(f[n - 1].begin(), f[n - 1].end(), 0L) % MOD;
}
// 降维
int distinctSubseqII2(string s) {
int f[26]{};
for (char c : s)
f[c - 'a'] = accumulate(f, f + 26, 1L) % MOD;
return accumulate(f, f + 26, 0L) % MOD;
}
// 再优化
int distinctSubseqII(string s) {
int total = 0, f[26]{};
for (char c : s) {
c -= 'a';
int others = total - f[c]; // total 中不含 f[c] 的部分（由于取模的原因，这里的减法可能会产生负数）
f[c] = 1 + total; // 更新 f[c]
total = ((f[c] + others) % MOD + MOD) % MOD; // 更新 total，并保证 total 非负
}
return total;
}
};
python3 解法, 执行用时: 48 ms, 内存消耗: 15.8 MB, 提交时间: 2023-10-09 09:43:12
'''
f[i][j] 表示用 s 的前 i 个字符组成以 j 结尾的不同非空子序列的个数
'''
MOD = 10 ** 9 + 7
class Solution:
def distinctSubseqII1(self, s: str) -> int:
f = [[0] * 26 for _ in range(len(s) + 1)]
for i, c in enumerate(s, 1):
c = ord(c) - ord('a')
f[i] = f[i - 1].copy()
f[i][c] = (1 + sum(f[i - 1])) % MOD
return sum(f[-1]) % MOD
'''
状态转移只发生在 i 和 i−1 之间，因此可以只用一个长为 26 的数组表示上述状态转移过程
除了 f[s[i]] 以外，其余值都不变，因此只需要更新 f[s[i]] 的值。
'''
def distinctSubseqII2(self, s: str) -> int:
f = [0] * 26
for c in s:
f[ord(c) - ord('a')] = (1 + sum(f)) % MOD
return sum(f) % MOD
'''
再优化，
'''
def distinctSubseqII(self, s: str) -> int:
total = 0
f = [0] * 26
for c in s:
c = ord(c) - ord('a')
others = total - f[c] # total 中不含 f[c] 的部分
f[c] = 1 + total # 更新 f[c]
total = (f[c] + others) % MOD # 更新 total
return total