| 日期 |
2022年9月17日 |
| 是否独立完成 |
否 |
| 涉及算法 |
动态规划 Again & Again |
题面
LeetCode 940. 不同的子序列 II
给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
- 例如，
"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。
示例 1：
1
2
3
| 输入：s = "abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
|
示例 2：
1
2
3
| 输入：s = "aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
|
示例 3：
1
2
3
| 输入：s = "aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
|
题解
动态规划
如果s中的字符是无重复的就很简单了，针对每个字符“取”或者“不取”都有两种可能，定义dp[i]为s前i个字母的不同非空子序列的个数，就可以引出转移公式dp[i+1]=dp[i]*2。
但是s中的字符是有重复的，所以要考虑去重的事。例如s="abb"，其中的a和两个b均能分别组成一次’ab’，所以要去掉一次，即dp[i+1]=dp[i]*2-dp[last]
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int distinctSubseqII(string s) {
int mod = 1e9+7;
int n = s.length();
vector<int> dp(n+1);
unordered_map<char,int> map;
dp[0]=1;
for(int i=0;i<n;i++){
dp[i+1]=dp[i]*2 % mod;
if(map.count(s[i])) dp[i+1]-=dp[map[s[i]]];
dp[i+1]%=mod;
map[s[i]]=i;
}
return (dp[n]-1+mod) % mod;
}
};
|