跳转至

940. 不同的子序列 II

题目描述

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

  • 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

 

示例 1：

输入：s = "abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

输入：s = "aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

输入：s = "aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

 

提示：

  • 1 <= s.length <= 2000
  • s 仅由小写英文字母组成

 

解法

方法一：动态规划

思考

不同非空子序列的个数，\(n\le 2000\)，不能枚举子集。以末字符分类：\(f[c]\) 表示当前以 \(c\) 结尾的不同子序列数。读入 \(c\) 时，它可以接在此前任意子序列之后，也可以单独成串，故 \(f[c]\leftarrow \sum f+1\)，重复字符会覆盖旧的以 \(c\) 结尾的集合。

我们定义 \(f[i]\) 表示以第 \(i\) 个小写字母结尾的不同子序列的个数。初始时 \(f\) 中所有元素均为 \(0\)。

遍历字符串 \(s\)，对于当前字符 \(c\)，我们将 \(f[c]\) 更新为 \(\sum_{i=0}^{25} f[i] + 1\)。其中 \(\sum_{i=0}^{25} f[i]\) 表示此前已经得到的所有不同子序列的个数，而 \(+1\) 表示字符 \(c\) 本身也可以作为一个子序列。

最后，答案为 \(\sum_{i=0}^{25} f[i]\)，对 \(10^9 + 7\) 取余。

时间复杂度 \(O(n \times C)\)，空间复杂度 \(O(C)\)。其中 \(n\) 是字符串 \(s\) 的长度，而 \(C\) 是字符集的大小，本题中 \(C = 26\)。

1
2
3
4
5
6
7
class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10**9 + 7
        f = [0] * 26
        for c in s:
            f[ord(c) - ord("a")] = (sum(f) + 1) % mod
        return sum(f) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int distinctSubseqII(String s) {
        final int mod = (int) 1e9 + 7;
        int[] f = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            int x = 1;
            for (int v : f) {
                x = (x + v) % mod;
            }
            f[s.charAt(i) - 'a'] = x;
        }
        int ans = 0;
        for (int v : f) {
            ans = (ans + v) % mod;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int distinctSubseqII(string s) {
        const int mod = 1e9 + 7;
        int f[26]{};
        for (char& c : s) {
            int x = 1;
            for (int v : f) {
                x = (x + v) % mod;
            }
            f[c - 'a'] = x;
        }
        int ans = 0;
        for (int v : f) {
            ans = (ans + v) % mod;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func distinctSubseqII(s string) int {
    const mod int = 1e9 + 7
    f := [26]int{}
    for _, c := range s {
        x := 1
        for _, v := range f {
            x = (x + v) % mod
        }
        f[c-'a'] = x
    }
    ans := 0
    for _, v := range f {
        ans = (ans + v) % mod
    }
    return ans
}

1
2
3
4
5
6
7
8
function distinctSubseqII(s: string): number {
    const mod = 1e9 + 7;
    const f: number[] = Array(26).fill(0);
    for (const c of s) {
        f[c.charCodeAt(0) - 97] = f.reduce((acc, v) => (acc + v) % mod, 1);
    }
    return f.reduce((acc, v) => (acc + v) % mod);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn distinct_subseq_ii(s: String) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let mut f = [0; 26];
        for u in s.bytes() {
            let mut x = 1;
            for &v in &f {
                x = (x + v) % MOD;
            }
            f[(u - b'a') as usize] = x;
        }
        f.iter().fold(0, |acc, &v| (acc + v) % MOD)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int distinctSubseqII(char* s) {
    const int mod = 1e9 + 7;
    int f[26] = {0};
    for (int i = 0; s[i]; ++i) {
        int x = 1;
        for (int j = 0; j < 26; ++j) {
            x = (x + f[j]) % mod;
        }
        f[s[i] - 'a'] = x;
    }
    int ans = 0;
    for (int i = 0; i < 26; ++i) {
        ans = (ans + f[i]) % mod;
    }
    return ans;
}

方法二：动态规划优化

思考

方法一每次更新要扫 \(26\) 个格子。维护总和 \(\textit{ans}\)，新增量为 \(\textit{ans}-f[i]+1\)，即可 \(O(1)\) 更新 \(f[i]\) 与 \(\textit{ans}\)。

在方法一的基础上，我们可以维护一个变量 \(\textit{ans}\) 表示当前 \(f\) 数组中所有元素的和。每次更新 \(f[i]\) 时，新增的不同子序列个数为 \(\textit{ans} - f[i] + 1\)，据此同时更新 \(\textit{ans}\) 与 \(f[i]\) 即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(C)\)。

相似题目：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10**9 + 7
        f = [0] * 26
        ans = 0
        for c in s:
            i = ord(c) - ord("a")
            add = (ans + 1 - f[i]) % mod
            ans = (ans + add) % mod
            f[i] = (f[i] + add) % mod
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int distinctSubseqII(String s) {
        final int mod = (int) 1e9 + 7;
        int[] f = new int[26];
        int ans = 0;
        for (int i = 0; i < s.length(); ++i) {
            int j = s.charAt(i) - 'a';
            int add = (ans + 1 + mod - f[j]) % mod;
            ans = (ans + add) % mod;
            f[j] = (f[j] + add) % mod;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int distinctSubseqII(string s) {
        const int mod = 1e9 + 7;
        int f[26]{};
        int ans = 0;
        for (char& c : s) {
            int i = c - 'a';
            int add = (ans + 1 + mod - f[i]) % mod;
            ans = (ans + add) % mod;
            f[i] = (f[i] + add) % mod;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func distinctSubseqII(s string) int {
    const mod int = 1e9 + 7
    f := [26]int{}
    ans := 0
    for _, c := range s {
        i := c - 'a'
        add := (ans + 1 + mod - f[i]) % mod
        ans = (ans + add) % mod
        f[i] = (f[i] + add) % mod
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function distinctSubseqII(s: string): number {
    const mod = 1e9 + 7;
    const f: number[] = Array(26).fill(0);
    let ans = 0;
    for (const c of s) {
        const i = c.charCodeAt(0) - 97;
        const add = (ans + 1 + mod - f[i]) % mod;
        ans = (ans + add) % mod;
        f[i] = (f[i] + add) % mod;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn distinct_subseq_ii(s: String) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let mut f = [0; 26];
        let mut ans = 0;
        for u in s.bytes() {
            let i = (u - b'a') as usize;
            let add = (ans + 1 + MOD - f[i]) % MOD;
            ans = (ans + add) % MOD;
            f[i] = (f[i] + add) % MOD;
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int distinctSubseqII(char* s) {
    const int mod = 1e9 + 7;
    int f[26] = {0};
    int ans = 0;
    for (int i = 0; s[i]; ++i) {
        int j = s[i] - 'a';
        int add = (ans + 1LL + mod - f[j]) % mod;
        ans = (ans + add) % mod;
        f[j] = (f[j] + add) % mod;
    }
    return ans;
}

评论