图解LeetCode——940. 不同的子序列 II（难度：困难）

一、题目

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

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

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

二、示例

2.1> 示例 1：

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

2.2> 示例 2：

【输入】s = "aba"
【输出】6
【解释】6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

2.3> 示例 3：

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

提示：

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

三、解题思路

根据题目描述，要找出一个字符串中所有不同的子序列。那么我们就需要找出这种子序列组合的规律。为了排除其他干扰，我们假设字符串中素有的字符都是不重复的。如下图所示，s=“abcd”，那么我们可以看到如下规律：

• 遍历第1个字符‘a’：子序列总数 = 1（字符‘a’本身）= 1
• 遍历第2个字符‘b’：子序列总数 =【字符'a'的子序列总数】+ 1（字符‘b’本身）= 1 + 1 = 2；
• 遍历第3个字符‘c’：子序列总数 =【字符'a'的子序列总数】+ 【字符'b'的子序列总数】+ 1（字符‘c’本身）= 1 + 2 + 1 = 4；
• 遍历第4个字符‘d’：子序列总数 =【字符'a'的子序列总数】+【字符'b'的子序列总数】+【字符'c'的子序列总数】+ 1（字符‘d’本身）= 1 + 2 + 4 + 1 = 8；
• 【总结果】 = 1 + 2 + 4 + 8 = 15

但是，题目中并没有限制字符不能重复，所以，我们这时候在考虑如果字符串中出现重复字符，对总结果的影响是怎样的？请见下图，我们以s=“abcb”为例，我们发现，里面有字符‘b’发生了重复，我们发现如下规律：

在第1次遍历到字符‘b’的时候：子序列为“ab”、“b”；
在第2次遍历到字符‘b’的时候：子序列为“ab”、“b”、“abb”、“bb”、“acb”、“abcb”、“bcb”、“cb”；
【结论】我们发现第2次遍历字符'b'的时候，已经包含了第1次遍历字符'b'的子序列了。所以，在统计最终结果的时候，我们需要把“上一次”相同字符子序列总数减去才可以。

基本思路就是这样了，具体代码实现，请参照如下部分。

四、代码实现

class Solution {
    public int distinctSubseqII(String s) {
        int mod = (int)1e9 + 7;
        long result = 0L;
        long[] letter = new long[26]; // 记录26个字符每个字符的子序列总数
        for (char sc : s.toCharArray()) {
            long pre = letter[sc - 'a']; // 获得字符sc前一次统计的子序列数
            letter[sc - 'a'] = (result + 1) % mod; // 计算当前字符sc的子序列数
            result = (result + letter[sc - 'a'] - pre + mod) % mod; // 加mod的目的是为了防止结果溢出为负数
        }
        return (int)result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」