【2022-10-14每日一题】940. 不同的子序列 II[Hard]
2022-10-14
2分钟阅读时长
2022-10-14每日一题：940. 不同的子序列 II
难度：Hard
标签：字符串 、 动态规划
给定一个字符串 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 <= 2000s仅由小写英文字母组成
方法一：动态规划
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
const mod int = 1e9+7
func distinctSubseqII(s string) int {
last := make([]int, 26)
for i := range last {
last[i] = -1
}
n := len(s)
f := make([]int, n)
for i, c := range s {
f[i] = 1 // 初始化
for _, j := range last {
if j != -1 { // 没有出现过 last[j]=−1
f[i] = (f[i]+f[j]) % mod
}
}
last[c-'a'] = i
}
ans := 0
for _, j := range last {
if j != -1 {
ans = (ans + f[j]) % mod
}
}
return ans
}
复杂度分析
时间复杂度：O(n∣Σ∣)，其中 n 是字符串 s 的长度，Σ 是字符集，在本题中 ∣Σ∣=26。即为动态规划需要的时间。
空间复杂度：O(n+∣Σ∣)。即为数组 f 和 last 需要的空间。
方法二：优化的动态规划
const mod int = 1e9+7
func distinctSubseqII(s string) int {
g := make([]int, 26)
for _, c := range s {
total := 1
for _, v := range g {
total = (total+v) % mod
}
g[c-'a'] = total
}
ans := 0
for _, v := range g {
ans = (ans + v) % mod
}
return ans
}
复杂度分析
时间复杂度：O(n∣Σ∣)，其中 n 是字符串 s 的长度，Σ 是字符集，在本题中 ∣Σ∣=26。即为动态规划需要的时间。
空间复杂度：O(∣Σ∣)。即为数组 g 和 last 需要的空间。
方法三：继续优化的动态规划
const mod int = 1e9+7
func distinctSubseqII(s string) int {
ans := 0
g := make([]int, 26)
for _, c := range s {
oi := c - 'a'
prev := g[oi]
g[oi] = (ans + 1) % mod // 更新 g[oi]
//当前序列的个数 = 之前的 + 新增的 - 重复的
ans = ((ans+g[oi]-prev)%mod+mod)%mod // 更新 ans，并保证 ans 非负
}
return ans
}
复杂度分析
时间复杂度：O(n+∣Σ∣)。其中 n 是字符串 s 的长度，Σ 是字符集，在本题中 ∣Σ∣=26。初始化需要的时间为 O(∣Σ∣)，动态规划需要的时间的为 O(n)。
空间复杂度：O(∣Σ∣)。即为数组 g 需要的空间。