题目要求
思路一：动态规划+转移优化
Java
class Solution {
public int distinctSubseqII(String s) {
int MOD = (int)1e9+7;
int res = 0;
int[] f = new int[26];
for (int i = 0; i < s.length(); i++) {
int cur = s.charAt(i) - 'a', pre = f[cur];
f[cur] = (res + 1) % MOD;
res = ((res + f[cur] - pre) % MOD + MOD) % MOD;
}
return res;
}
}
- 时间复杂度：O(n×C)
- 空间复杂度：O(C)
C++
class Solution {
public:
int distinctSubseqII(string s) {
int MOD = (int)1e9+7;
int res = 0;
int f[26];
memset(f, 0, sizeof(f));
for (int i = 0; i < s.size(); i++) {
int cur = s[i] - 'a', pre = f[cur];
f[cur] = (res + 1) % MOD;
res = ((res + f[cur] - pre) % MOD + MOD) % MOD;
}
return res;
}
};
- 时间复杂度：O(n×C)
- 空间复杂度：O(C)
Rust
impl Solution {
pub fn distinct_subseq_ii(s: String) -> i32 {
let MOD = 1000000007;
let mut res = 0;
let mut f = vec![0; 26];
for cur in s.chars() {
let i = cur as u8 - 'a' as u8;
let pre = f[i as usize];
f[i as usize] = (res + 1) % MOD;
res = ((res + f[i as usize] - pre) % MOD + MOD) % MOD;
}
res
}
}
- 时间复杂度：O(n×C)
- 空间复杂度：O(C)
思路二：求和（调api）
- 思路和上面相似，但更简单粗暴一点，f[i]依旧用于记录以当前字符为末尾的子串数量，在每次遍历中计算整个数组的和（即当前的全部子串数量），然后加上自己的单字符串，表示为f[i]=sum(f)+1，答案即为整个数组的和；
- 此处规避掉了重复字符的讨论，因为相同字符后面的会覆盖前面的，可以看作每次遍历都在已有子串的基础上加一个字符【md我在说什么，举个例子吧】；
栗子【vonvv】：
| 当前遍历字符 | f[i] | 子串 |
|---|---|---|
| v | 1 | v |
| o | 2 | vo，o |
| n | 4 | vn，von，on，n |
| v | 8 | vv，vov，ov，vnv，vonv，onv，nv，v |
| v | 15 | vv，vov，ov，vnv，vonv，onv，nv，vvv，vovv，ovv，vnvv，vonvv，onvv，nvv，vv，v |
最终即为三个字符对应值相加f[o]+f[n]+f[v]=2+4+15=21
注意！！！
因为要计算sum(f)，这值可能会超级大，所以要用long型！
Java
class Solution {
public int distinctSubseqII(String s) {
int MOD = (int)1e9+7;
long[] f = new long[26];
for (char cur : s.toCharArray()) {
f[cur - 'a'] = Arrays.stream(f).sum() % MOD + 1;
}
return (int)(Arrays.stream(f).sum() % MOD);
}
}
- 时间复杂度：O(n×C)
- 空间复杂度：O(C)
C++
class Solution {
public:
int distinctSubseqII(string s) {
int MOD = (int)1e9+7;
vector<long> f(26, 0);
for (auto cur : s) {
f[cur - 'a'] = accumulate(f.begin(), f.end(), 1l) % MOD;
}
return accumulate(f.begin(), f.end(), 0l) % MOD;
}
};
- 时间复杂度：O(n×C)
- 空间复杂度：O(C)
Rust
- get了求和函数的奇妙调用【但没完全get】
impl Solution {
pub fn distinct_subseq_ii(s: String) -> i32 {
let MOD = 1000000007;
let mut f = vec![0; 26];
for cur in s.chars() {
f[(cur as u8 - 'a' as u8) as usize] = f.iter().sum::<i64>() % MOD + 1;
}
(f.iter().sum::<i64>() % MOD) as i32
}
}
- 时间复杂度：O(n×C)
- 空间复杂度：O(C)
总结
完全没思路的一道题~是那种望而生畏，读完题失去梦想，看完题解觉得自己是傻子的类型……
看普通动规的题解感觉好难理解，差点放弃，然后跳到后面理清思路返回来就好理解很多，但还是只选了两种比较简洁的方式写；
以上就是Java C++题解eetcode940不同的子序列 II的详细内容，更多关于Java C++ 不同的子序列的资料请关注编程网其它相关文章！
