Java&C++题解与拓展——leetcode940.不同的子序列 II【么的新知识？】

站长

2023年01月04日 08:18 · 阅读数 10

每日一题做题记录，参考官方和三叶的题解

题目要求

Java&C++题解与拓展——leetcode940.不同的子序列 II【么的新知识？】

思路一：动态规划+转移优化

定义一个数组记录以每个字母f[i]f[i]f[i]为结尾会有几种子序列；
遍历字符串，计算每个字符对应的f[i]f[i]f[i]；
- 第一个字符仅有自己，f[0]=res=1f[0]=res=1f[0]=res=1；
- 后续子串的构造方式相似：
  - 为在之前出现的所有子串末尾加上自己，并加上仅有自己的单字符串，表示为f[i]=res+1f[i]=res+1f[i]=res+1；
  - 更新答案字符串为res+=f[i]res+=f[i]res+=f[i]；
  - 但存在字母重复的可能，所以要提前存好更新前的f[i]f[i]f[i]，也就是上一次对该字符的计算结果pre，然后计算二者差值加在答案上，表示为res+=f[i]−preres+=f[i]-preres+=f[i]−pre。

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(n\times C)O(n×C)
空间复杂度：O(C)O(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(n\times C)O(n×C)
空间复杂度：O(C)O(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(n\times C)O(n×C)
空间复杂度：O(C)O(C)O(C)

思路二：求和（调api）

思路和上面相似，但更简单粗暴一点，f[i]f[i]f[i]依旧用于记录以当前字符为末尾的子串数量，在每次遍历中计算整个数组的和（即当前的全部子串数量），然后加上自己的单字符串，表示为f[i]=sum(f)+1f[i]=sum(f)+1f[i]=sum(f)+1，答案即为整个数组的和；
此处规避掉了重复字符的讨论，因为相同字符后面的会覆盖前面的，可以看作每次遍历都在已有子串的基础上加一个字符【md我在说什么，举个例子吧】；

栗子【vonvv】：

当前遍历字符	f[i]f[i]f[i]	子串
`v`	111	`v`
`o`	222	`vo`，`o`
`n`	444	`vn`，`von`，`on`，`n`
`v`	888	`vv`，`vov`，`ov`，`vnv`，`vonv`，`onv`，`nv`，`v`
`v`	151515	`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=21f[o]+f[n]+f[v]=2+4+15=21f[o]+f[n]+f[v]=2+4+15=21。

注意！！！因为要计算sum(f)sum(f)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(n\times C)O(n×C)
空间复杂度：O(C)O(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(n\times C)O(n×C)
空间复杂度：O(C)O(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(n\times C)O(n×C)
空间复杂度：O(C)O(C)O(C)

总结

完全没思路的一道题~是那种望而生畏，读完题失去梦想，看完题解觉得自己是傻子的类型……
看普通动规的题解感觉好难理解，差点放弃，然后跳到后面理清思路返回来就好理解很多，但还是只选了两种比较简洁的方式写；
被一堆事情搅得乱七八糟的一天【周】，本来可以快乐写代码……

欢迎指正与讨论！