文章目录
前言
解题思路
没有重复字符的时候
有重复字符的时候
代码
前言
给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
例如，“ace” 是 “abcde” 的一个子序列，但 “aec” 不是
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/distinct-subsequences-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
没有重复字符的时候
新的子串为{1}
2到来,新加{2},{1,2}
3到来,数量是之前的2倍
{3},{1,3},{2,3},{1,2,3}
有重复字符的时候
第二个1到来,重复了{1},因此新增数量为1
第三个1来了,重复了2个
因此可以推出,假设之前出现的字母的数量为X=100;
那么当下一次出现相同字母的数量为
all=perAll(上一个位置的all)+newAll(如果不重复字母新增的数量)-X;
用一个数组存储26个字母结尾的字符串数量，
all加上之前的all,如果出现过相同的字母,就减去数组中的相同字母的数
来到b,all=2
空串和{b}
来到第一个c,newAll=2,all=4,记录c:2
来到第2个c,newAll=4,all=8
因为c有记录,因此all要减2,
代码
class Solution {
public int distinctSubseqII(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str=s.toCharArray();
int all=1;
int mod=1000000007;
int[] map=new int[26];
for(int i=0;i<str.length;i++){
int newAll=all;
int curAll=(all+newAll)%mod;
all=(curAll-map[str[i]-'a']+mod)%mod;
map[str[i]-'a']=newAll;
}
return all-1;
}
}
