2022-10-01:给定一个字符串 s,计算 s 的 不同非空子序列 的个数 因为结果可能很大,所以返回答

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代码

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
464
粉丝
21
喜欢
37
收藏
22
排名:461
访问:1.9 万
私信
所有博文
社区赞助商