LC 940. 不同的子序列 II

题目描述

这是 LeetCode 上的 940. 不同的子序列 II ,难度为 困难

给定一个字符串 s,计算 s 的 不同非空子序列 的个数。

因为结果可能很大,所以返回答案需要对 $10^9 + 7$ 取余 。

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

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

示例 1:

1
2
3
4
5
输入:s = "abc"

输出:7

解释:7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"

示例 2:
1
2
3
4
5
输入:s = "aba"

输出:6

解释:6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"

示例 3:
1
2
3
4
5
输入:s = "aaa"

输出:3

解释:3 个不同的子序列分别是 "a", "aa" 以及 "aaa"

提示:

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

序列 DP

为了方便,我们令 s 下标从 $1$ 开始,定义 $f[i][j]$ 为考虑前 $i$ 个字符,且结尾字符为 $j$ 的不同子序列的个数,其中 $j$ 的范围为 $[0, 25]$ 代指小写字符 a-z

我们有显而易见的初始化条件 $f[0][X] = 0$,最终答案为 $\sum_{i = 0}^{25}f[n][i]$。

不失一般性考虑 $f[i][j]$ 该如何转移,根据 $s[i]$ 是否为 $j$ 进行分情况讨论:

  • $s[i] \neq j$ : 由于状态定义限定了结尾字符必须是 $j$,因而 $s[i]$ 必然不会用到,此时有:
  • $s[i] = j$ : 此时 $s[i]$ 可作为结尾元素,同时由于我们统计的是「不同」的子序列个数,因而「以 $j$ 结尾的子序列方案数」与「以 $s[i]$ 结尾的子序列方案数」完全等价。
    对于以 $s[i]$ 作为子序列结尾字符的方案数,容易想到其方案数等于「$s[i]$ 单独作为子序列」+「$s[i]$ 拼接在其余子序列后面形成新子序列」,即有:

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
int MOD = (int)1e9+7;
public int distinctSubseqII(String s) {
int n = s.length(), ans = 0;
int[][] f = new int[n + 1][26];
for (int i = 1; i <= n; i++) {
int c = s.charAt(i - 1) - 'a';
for (int j = 0; j < 26; j++) {
if (c != j) {
f[i][j] = f[i - 1][j];
} else {
int cur = 1;
for (int k = 0; k < 26; k++) cur = (cur + f[i - 1][k]) % MOD;
f[i][j] = cur;
}
}
}
for (int i = 0; i < 26; i++) ans = (ans + f[n][i]) % MOD;
return ans;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int distinctSubseqII(string s) {
int n = s.length(), MOD = 1e9 + 7;
vector<vector<int>> f(n + 1, vector<int>(26, 0));
for (int i = 1; i <= n; ++i) {
int c = s[i - 1] - 'a';
for (int j = 0; j < 26; ++j) {
if (c != j) {
f[i][j] = f[i - 1][j];
} else {
int cur = 1;
for (int k = 0; k < 26; ++k) cur = (cur + f[i - 1][k]) % MOD;
f[i][j] = cur;
}
}
}
int ans = 0;
for (int i = 0; i < 26; ++i) ans = (ans + f[n][i]) % MOD;
return ans;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
class Solution:
def distinctSubseqII(self, s: str) -> int:
n, MOD = len(s), 1e9+7
f = [[0] * 26 for _ in range(n + 1)]
for i in range(1, n + 1):
c = ord(s[i - 1]) - ord('a')
for j in range(26):
f[i][j] = f[i - 1][j] if c != j else (1 + sum(f[i - 1])) % MOD
return int(sum(f[n]) % MOD)

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function distinctSubseqII(s: string): number {
const MOD = 1e9+7
let n = s.length, ans = 0
const f = new Array<Array<number>>(n + 1)
for (let i = 0; i <= n; i++) f[i] = new Array<number>(26).fill(0)
for (let i = 1; i <= n; i++) {
const c = s.charCodeAt(i - 1) - 'a'.charCodeAt(0)
for (let j = 0; j < 26; j++) {
if (c != j) {
f[i][j] = f[i - 1][j]
} else {
let cur = 1
for (let k = 0; k < 26; k++) cur = (cur + f[i - 1][k]) % MOD
f[i][j] = cur
}
}
}
for (let i = 0; i < 26; i++) ans = (ans + f[n][i]) % MOD
return ans
}

  • 时间复杂度:$O(n \times C^2)$,其中 $C = 26$ 为字符集大小
  • 空间复杂度:$O(n \times C)$

转移优化

根据转移的依赖关系,实现上,我们并不需要真正记录每一个 $f[i][X]$,而可以直接记录一个总的不同子序列方案数 ans

这可以避免每次计算新状态时,都累加前一个 $f[i - 1][X]$ 的值,有效减低时空复杂度。

Java 代码:

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

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int distinctSubseqII(string s) {
int n = s.length(), ans = 0, MOD = 1e9 + 7;
vector<int> f(26, 0);
for (int i = 0; i < n; ++i) {
int c = s[i] - 'a', prev = f[c];
f[c] = (ans + 1) % MOD;
ans = (ans + f[c]) % MOD;
ans = (ans - prev + MOD) % MOD;
}
return ans;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
class Solution:
def distinctSubseqII(self, s: str) -> int:
n, MOD, ans = len(s), 1e9+7, 0
f = [0] * 26
for i in range(n):
c = ord(s[i]) - ord('a')
prev = f[c]
f[c] = (ans + 1) % MOD
ans = (ans + f[c] - prev) % MOD
return int(ans)

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
function distinctSubseqII(s: string): number {
const MOD = 1e9+7
let n = s.length, ans = 0
const f = new Array<number>(26).fill(0)
for (let i = 0; i < n; i++) {
const c = s.charCodeAt(i) - 'a'.charCodeAt(0), prev = f[c]
f[c] = (ans + 1) % MOD
ans = (ans + f[c]) % MOD
ans = (ans - prev + MOD) % MOD
}
return ans
}

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(C)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.940 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。