940. Distinct Subsequences II

Given a string S, count the number of distinct, non-empty subsequences of S .

Since the result may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".

Example 2:

Input: "aba"
Output: 6 Explanation: The 6 distinct subsequences are "a", "b", "ab", "ba", "aa" and "aba".

Example 3:

Input: "aaa"
Output: 3 Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".

Note:

  1. S contains only lowercase letters.
  2. 1 <= S.length <= 2000

这道题是之前那道 Distinct Subsequences 的类似题目,这里只有一个字符串,让找出所有不同的子序列,如果字符串中没有重复字符,可以直接得到子序列的个数,但是这里由于重复字符的存在,就大大增加了难度。由于题目中提示了结果可能非常大,要对一个超大数取余,就相当于明确说了要用动态规划 Dynamic Programming 来做,下面就要来考虑 dp 数组的定义和状态转移方程的推导了。刚开始博主也是考虑用一个一维数组 dp,其中 dp[i] 表示以 S[i] 结尾的不同子序列的个数,就像 这个帖子 中定义的一样,但是状态转移方程不好推导,那个帖子虽然代码可以跑通,但是解释的却不通,博主也纳闷这算是歪打正着么,希望哪位大神来解释一下。这里还是根据 lee215 大神的帖子 来讲解吧。这里使用一个大小为 26 的一维数组 dp,其中 dp[i] 表示以字符 i+’a’ 结尾的不同子序列的个数,因为题目中限定了只有小写字母,所以只有 26 个。以 aba 这个例子来分析一下,当遇到开头的a时,那么以a结尾的子序列只有一个,就是a,当遇到中间的b时,此时知道以b结尾的子序列有2个,分别是 b 和 ab,是怎么得来的呢,其实是空串和a后面分别加个b得来的,此时貌似得到的值和通过 sum(dp)+1 计算的结果相等,再来验证一下这个成不成立。当遇到末尾的a的时候,那么此时以a结尾的子序列就有4个,分别是 a,aa,ba,aba,是怎么得来的?在这个a加入之前,当前所有的子序列有,a,b,ab,如果再算上一个空串,[],a,b,ab,则在其后面各加上一个b,就可以得到结果了,貌似也符合 sum(dp)+1 的规律,这其实也并不难理解,因为在当前不同序列的基础上,加上任何一个字符都会得到另一个不同的子序列,后面的加1是为了加上空串的情况,这个就是状态转移方程了,最终的结果是把 dp 数组累加起来取余后返回即可,参见代码如下:
解法一:

class Solution {
public:
    int distinctSubseqII(string S) {
        int M = 1e9 + 7;
        vector<int> dp(26);
        for (char c : S) {
            dp[c - 'a'] = accumulate(dp.begin(), dp.end(), 1L) % M;
        }
        return accumulate(dp.begin(), dp.end(), 0L) % M;
    }
};

这里还有另一种解法,由热心网友一切忘记回忆提供,博主觉得思路很巧妙,故而收录进来,特此感谢一下。这种解法是要建立两个一维的 dp 数组,其中 a[i] 表示以 S[i] 字符结尾的不同子序列个数,b[i] 表示不以 S[i] 字符结尾的不同子序列的个数,初识时 a[0] = 1, b[0] = 0。然后就是来推导状态转移方程了,其中 b[i] 比较简单,因为不用加上 S[i] 字符,其就更新为前一个位置的两个状态之和,b[i] = a[i-1] + b[i-1]。关键是 a[i] 稍微复杂一些,需要分情况讨论一下,假如 S[i] 这个字符之前没有出现过,那么目前所有出现的情况后面加上这个新的字符都是不同的,另外再加上这个单独的字符的一种情况,所以更新为 b[i]+1,因为此时的 b[i] 已经更新为不包括 S[i] 的所有不同子序列个数。当 S[i] 在之前出现过的话,那么就有可能出现重复情况,具体重复的数量就是上一次出现这个字符的位置时候的b值。因为如果选择加上了当前这个字符,那么所有上一次出现这个字符的地方之前的子序列就都不能选择了,所以要减去上一次的b值,为了快速知道每次的b值,用一个 HashMap 建立每个字符和其对应的b值即可,参见代码如下:
解法二:

class Solution {
public:
    int distinctSubseqII(string S) {
        int n = S.size(), res = 0, M = 1e9 + 7;
        unordered_map<char, long> m;
        vector<long> a(n), b(n);
        a[0] = 1;
        m[S[0]] = 0;
        for (int i = 1; i < n; ++i) {
            b[i] = (a[i - 1] + b[i - 1]) % M;
            if (!m.count(S[i])) {
                a[i] = (b[i] + 1) % M;
            } else {
                a[i] = (M + b[i] - m[S[i]]) % M;
            }
            m[S[i]] = b[i];
        }
        return (a.back() + b.back()) % M;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/940

类似题目:

Distinct Subsequences

参考资料:

https://leetcode.com/problems/distinct-subsequences-ii/

https://leetcode.com/problems/distinct-subsequences-ii/discuss/192017/C%2B%2BJavaPython-4-lines-O(N)-Time-O(1)-Space

https://leetcode.com/problems/distinct-subsequences-ii/discuss/192030/Java-DP-O(N2)-time-greater-O(N)-time-greater-O(1)-space

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation