写点什么

2022-10-01:给定一个字符串 s,计算 s 的 不同非空子序列 的个数 因为结果可能很大,所以返回答案需要对 10^9 + 7 取余 。 字符串的 子序列 是经由原字符串删除一些(也可能不删除

  • 2022 年 10 月 01 日
    北京
  • 本文字数:997 字

    阅读完需:约 3 分钟

2022-10-01:给定一个字符串 s,计算 s 的 不同非空子序列 的个数 因为结果可能很大,所以返回答案需要对 10^9 + 7 取余 。 字符串的 子序列 是经由原字符串删除一些(也可能不删除

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

发布于: 刚刚阅读数: 3
用户头像

还未添加个人签名 2021.02.15 加入

还未添加个人简介

评论

发布
暂无评论
2022-10-01:给定一个字符串 s,计算 s 的 不同非空子序列 的个数 因为结果可能很大,所以返回答案需要对 10^9 + 7 取余 。 字符串的 子序列 是经由原字符串删除一些(也可能不删除_算法_福大大架构师每日一题_InfoQ写作社区