[LeetCode] 940. Distinct Subsequences II

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)