C ++中的不同子序列II

假设我们有一个字符串S，我们必须计算S的不同子序列数。结果可能很大，因此我们将以10 ^ 9 + 7为模返回答案。

因此，如果输入像“ bab”，那么输出将为6，因为有6个不同的序列，分别是“ a”，“ b”，“ ba”，“ ab”，“ bb”，“ abb”。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数add()，这将需要a，b，

• 返回（（a mod MOD）+（b mod MOD））mod MOD

• 定义一个函数sub()，这将需要a，b，

• 返回（（（（a mod MOD）-（b mod MOD））+ MOD）mod MOD

• 定义一个函数mul()，这将需要a，b，

• 返回（（a mod MOD）*（b mod MOD））mod MOD

• 从主要方法来看，所以以下内容-

• n：= s的大小

• 定义大小为26的数组dp

• res：= 0

• s：=在s之前连接空间

• 对于初始化i：= 1，当i <= n时，更新（将i增加1），-

• x：= s [i]

• 添加：= sub（add(res,1)，dp [x-'a']）

• dp [x-'a'] = add（dp [x-'a']，已添加）

• res：=添加（res，添加）

• 返回资源

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
   public:
   lli add(lli a, lli b){
      return ( (a % MOD) + (b % MOD) ) % MOD;
   }
   lli sub(lli a, lli b){
      return ( ( (a % MOD) - (b % MOD) ) + MOD ) % MOD;
   }
   lli mul(lli a, lli b){
      return ( (a % MOD) * (b % MOD) ) % MOD;
   }
   int distinctSubseqII(string s) {
      int n = s.size();
      vector <lli> dp(26);
      int res = 0;
      s = " " + s;
      for(lli i = 1; i <= n; i++){
         char x = s[i];
         int added = sub(add(res, 1) , dp[x - 'a']);
         dp[x - 'a'] = add(dp[x - 'a'], added);
         res = add(res, added);
      }
      return res;
   }
};
main(){
   Solution ob;
   cout << (ob.distinctSubseqII("bab"));
}

输入值

"bab"

输出结果

6