2022-10-01：给定一个字符串 s，计算 s 的 不同非空子序列 的个数
因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符
但不改变剩余字符相对位置的一个新字符串。
输入: s = “abc”。
输出: 7。
答案2022-10-01：
dp[0~25]，保存26个字母结尾的子序列个数。
时间复杂度：O(N)。
空间复杂度：O(1)。
代码用rust编写。代码如下：
use std::collections::HashMap;
fn main() {
let ans = distinct_subseq_ii("bccaccbaabbc");
println!("ans = {}", ans);
let ans = zuo("bccaccbaabbc");
println!("ans = {}", ans);
}
fn distinct_subseq_ii(s: &str) -> i32 {
if s.len() == 0 {
return 0;
}
let m = 1000000007;
let str2: Vec<u8> = s.bytes().collect();
// a -> 0 ->
// b -> 1 ->
// c -> 2 ->
// z -> 25 ->
// count[i] = 0
let mut count = [0; 26];
// { }
let mut all = 1; // 算空集
for x in str2.iter() {
// x
// 纯新增
// add = all - count[x]
// all += add
// count[x] + add
let add = (all - count[(*x - 'a' as u8) as usize] + m) % m;
all = (all + add) % m;
count[(*x - 'a' as u8) as usize] = (count[(*x - 'a' as u8) as usize] + add) % m;
}
// {} 去掉！
return all - 1;
}
fn zuo(s: &str) -> i32 {
if s.len() == 0 {
return 0;
}
let m = 1000000007;
let str2: Vec<u8> = s.bytes().collect();
let mut map: HashMap<u8, i32> = HashMap::new();
let mut all = 1; // 一个字符也没遍历的时候，有空集
for x in str2.iter() {
let new_add = all;
// int curAll = all + newAdd - (map.containsKey(x) ? map.get(x) : 0);
let mut cur_all = all;
cur_all = (cur_all + new_add) % m;
cur_all = (cur_all
- if map.contains_key(x) {
*map.get(x).unwrap()
} else {
0
}
+ m)
% m;
all = cur_all;
map.insert(*x, new_add);
}
return all - 1;
}
执行结果如下：
左神java代码
