算法leetcode

力扣940-不同的子序列

字数统计: 1.2k字   |   阅读时长: 5分
, , , ,

摘要: 不同的子序列

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

本文我们继续看一个比较难的问题 力扣940-不同的子序列，与昨天的题目 力扣730-统计不同回文子序列 非常类似。算法的核心是动态规划，根据动态规划阶段的不同选取方式，有普通的一维线性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