Keshawn_lu's Blog

Leetcode 940. 不同的子序列 II

动态规划
字数统计: 571阅读时长: 2 min
2022/10/14 Share

题目简介：

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

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

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

示例 1：

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

示例 2：

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

提示：

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

思路：

我们可以发现，若f[i]是以s[i]为结尾的子序列的数目，那么我们可以枚举倒数第二个字符来进行状态转移，因此：

  • f[i] = f[0] + ... + f[i - 1] + 1（1为只有s[i]的情况）

但是这样会产生重复计数，因此我们选出每个字母最后出现的位置（并且在i之前），那么就变成了：

  • f[i] = f[last[0]] + ... + f[last[25]] + 1（26个字母）

于是我们可以设置一个数组dp来保存每个字母最后出现位置时的子序列数量，假设我们遍历到s[i]，s[i]为第j个字母，那么就可以更新：

  • $dp[j] = 1 + \sum\limits_{0 \leq k \lt 26}dp[k]$

所有都遍历完成后，dp[i]便是以当前字母为结尾的子序列数量。

因此，最后我们只要累加dp[0] + ... + dp[25]即可。

代码如下：

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
class Solution {
public:

    int distinctSubseqII(string s) {

        int mod_num = pow(10, 9) + 7;

        int dp[26] = {0};   //dp[i]代表以字母i结尾的子序列数量

        for(int i = 0; i < s.size(); i++){

            int sum = 1;
            for(int j = 0; j < 26; j++){

                sum = (sum + dp[j]) % mod_num;
            }

            dp[s[i] - 'a'] = sum;   //更新以字母i结尾的子序列数量(以最后一次出现的位置为准)
        }

        int res = 0;

        for(int i = 0; i < 26; i++){

            res = (res + dp[i]) % mod_num;
        }

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网