Leetcode 940. 不同的子序列 II

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

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

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

示例 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 <= s.length <= 2000
• s 仅由小写英文字母组成

我的想法：
1.最开始是想着新搞一个 list 为 somelist ，把第一个字符放进去。从第二个字符遍历字符串 s ，复制 somelist 到 hhh 。遍历 somelist ，把 s[i] 加 hhh 里 ，把somelist + s[i] 加里。复制 hhh 到 somelist 。最后把 somelist 去重 取长度。

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        somelist = list()
        slist = list(s)
        somelist.append(slist[0])
        print(somelist)
        for c in s[1:]:
            hhh = somelist[:]
            for ch in somelist:
                hhh.append(c)
                hhh.append(c+ch)
            somelist = hhh[:]
        return len(set(somelist))
1
2
3
4
5
6
7
8
9
10
11
12
13

直接超时。

2. 然后看了这个题解，打算自己找找规律。
   

例如 l e e:
“” l （遍历到 l ，新增 1 个）
“” l e le （遍历到 e ，新增 2 个）
“” l e le e le ee lee （遍历到 e ，新增 4 个，有 1 个重复）

a a a:
“” a (遍历到 a ，新增 1 个）
“” a a aa (遍历到 a ，新增 2 个，有 1 个重复）
“” a aa a aa aaa (遍历到 a ，新增 3 个，有 2 个重复）

a b a b b:
“” a (遍历到 a ，新增 1 个）
“” a b ab (遍历到 b ，新增 2 个）
“” a b ab a aa ba aba (遍历到 a ，新增 4 个，有 1 个重复）
“” a b ab aa ba aba b ab bb abb aab bab abab (遍历到 b ，新增 7 个，有 2 个重复）
“” a b ab aa ba aba bb abb aab bab abab b ab bb abb aab bab abab bbb abbb aabb babb ababb (遍历到 b ，新增 12 个，有 7 个重复）

https://leetcode.cn/problems/distinct-subsequences-ii/solutions/1890717/bu-tong-by-capital-worker-vga3/
那么就像题解说的，“遍历到的第二个字符b，出现重复的序列为b和ab，而这两个序列正好是上一次添加b（也就是第②步）的时候新增的两个序列。”，这个新增的序列不是指去重之后的，是指去重之前的。

我是使用了个字典来存储，key 为遍历对应的字符，如果这个字符在字典里，就将times 减去对应的 value 值，即重复值。之后更新重复值。

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        repeatdict = defaultdict()
        times = 1
        for ch in s:
            oldtime = times
            times *= 2
            if ch in repeatdict.keys():
                times = times - repeatdict[ch]
            repeatdict[ch] = oldtime
        return (times - 1) % 1000000007
1
2
3
4
5
6
7
8
9
10
11

其他看不懂的题解也粘上来，万一什么时候看懂了呢
https://leetcode.cn/problems/distinct-subsequences-ii/solutions/1888523/bu-tong-de-zi-xu-lie-ii-by-leetcode-solu-k2h5/

https://leetcode.cn/problems/distinct-subsequences-ii/solutions/1890903/by-ac_oier-ph94/