力扣940-不同的子序列

  |  

摘要: 不同的子序列

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们看一个比较难的问题,算法的核心是动态规划,根据动态规划阶段的不同选取方式,有普通的一维线性DP,以及序列自动机两种做法。

题目

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

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

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

提示:

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

示例 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:动态规划

首先需要通过对比较小的 n 进行手算,发现隐晦的递推关系,于是才能写出动态规划算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
状态定义:
dp[i] := 考虑前 i 个元素 s[0..i-1],不同的子序列个数,含空串

初始化:
dp[0] = 1

答案:
dp[n] - 1

状态转移:
dp[i] = dp[i - 1] 不选 s[i - 1]
+ (dp[i - 1] - dp[last[s[i-1]-'a'] - 1]) 选择 s[i - 1]
last[s[i-1]-'a'] = i
其中 last[ch] := 在 i 之前最后一次出现 ch 的位置

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using ll = long long;
const int MOD = 1e9 + 7;

class Solution {
public:
int distinctSubseqII(string S) {
if(S.empty())
return 0;
int n = S.size();
if(n == 1)
return 1;
vector<int> dp(n + 1, 0);
// dp[i] := 考虑前 i 个元素,不同的子序列个数
vector<int> last(26, -1); // 字符上一次出现的位置,转移时有用, -1 表示没出现过
dp[0] = 1; // 不考虑任何字符时候,有个空串
for(int i = 1; i <= n; ++i)
{
dp[i] = (2 * (ll)dp[i - 1]) % MOD;
if(last[S[i - 1] - 'a'] >= 1)
dp[i] = (dp[i] - dp[last[S[i - 1] - 'a'] - 1] + MOD) % MOD;
last[S[i - 1] - 'a'] = i;
}
return dp[n] - 1;
}
};

算法2:序列自动机

首先建立字符串 $S$ 的序列自动机,然后再序列自动机上进行动态规划,定义以下状态:

1
dp[i] := 从序列自动机的状态节点 i 出发可以取到的不同的子序列个数,含空串

如果从状态节点 i 经过字符 ch 对应的边可以到达状态节点 j,那么状态转移方程如下:

上面公式中的 1 表示的是除了选择各个 ch 的贡献,还有不选任何字符形成空串的贡献。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
using ll = long long;
const int MOD = 1e9 + 7;

class SeqAM
{
public:
SeqAM(){}
SeqAM(const string& t)
{
build(t);
}

void build(const string& t)
{
// 由字符串 t 建立序列自动机
int n = t.size();
int m = 26; // 字母表中的字符数
nxt.assign(n + 1, vector<int>(m, -1)); // 状态节点 0 ~ n,字母表 0 ~ m-1

for(int i = n - 1; i >= 0; --i)
{
for(int ch = 0; ch < 26; ++ch)
nxt[i][ch] = nxt[i + 1][ch];
nxt[i][t[i] - 'a'] = i + 1;
}
}

bool find(const string& s) const
{
int l = s.size();
int p = 0; // 初始状态
for(int i = 0; i < l; ++i)
{
p = nxt[p][s[i] - 'a'];
if(p == -1)
return false;
}
return true;
}

int check_nxt(int i, int ch) const
{
return nxt[i][ch];
}

private:
vector<vector<int>> nxt;
};

int dfs(int i, vector<int>& dp, const SeqAM& seq_am)
{
int n = dp.size();
if(dp[i] != -1)
return dp[i];

dp[i] = 0;
for(int ch = 0; ch < 26; ++ch)
{
int nxt_i = seq_am.check_nxt(i, ch);
if(nxt_i != -1)
dp[i] = (dp[i] + dfs(nxt_i, dp, seq_am)) % MOD;
}
dp[i] = ((ll)dp[i] + 1) % MOD;
return dp[i];
}

class Solution {
public:
int distinctSubseqII(string S) {
if(S.empty())
return 0;
int n = S.size();
if(n == 1)
return 1;
SeqAM seq_am(S);
vector<int> dp(n + 1, -1);
return ((ll)dfs(0, dp, seq_am) - 1 + MOD) % MOD;
}
};

Share