免费建立企业网站,app 网站开发公司,盐城网站建设首选梦搏网络,程序外包平台文章目录1. 题目2. 解题1. 题目
给定一个字符串 S#xff0c;计算 S 的不同非空子序列的个数。
因为结果可能很大#xff0c;所以返回答案模 10^9 7.
示例 1#xff1a;
输入#xff1a;abc
输出#xff1a;7
解释#xff1a;7 个不同的子序列分别是 计算 S 的不同非空子序列的个数。
因为结果可能很大所以返回答案模 10^9 7.
示例 1
输入abc
输出7
解释7 个不同的子序列分别是 a, b, c, ab, ac, bc, 以及 abc。示例 2
输入aba
输出6
解释6 个不同的子序列分别是 a, b, ab, ba, aa 以及 aba。示例 3
输入aaa
输出3
解释3 个不同的子序列分别是 a, aa 以及 aaa。提示
S 只包含小写字母。
1 S.length 2000来源力扣LeetCode 链接https://leetcode-cn.com/problems/distinct-subsequences-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution {
public:int distinctSubseqII(string S) {int n S.size(), mod 1e97;vectorint dp(n1, 0);dp[0] 1;//空字符串vectorint prev(26, -1);// 之前最近的相同字符 posfor(int i 0; i n; i) {dp[i1] (dp[i]*2)%mod;// 当前字符跟之前的结合不结合产生的方案数if(prev[S[i]-a] ! -1)// 之前有重复的 相同字符会产生重复计数dp[i1] (dp[i1]-dp[prev[S[i]-a]]mod)%mod;prev[S[i]-a] i;//更新最近的字符位置}return dp[n]-1;}
};0 ms 7.1 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
