C++의 고유한 하위 시퀀스 II

<시간/>

문자열 S가 있다고 가정하고 S의 고유한 하위 시퀀스 수를 계산해야 합니다. 결과가 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.

따라서 입력이 "bab"과 같으면 출력은 "a", "b, "ba", "ab", "bb", "abb"의 6가지 다른 시퀀스가 있으므로 6이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

add() 함수를 정의하면, b,
return ((a mod MOD) + (b mod MOD)) mod MOD
함수 sub()를 정의하면, b,
return (((a mod MOD) - (b mod MOD)) + MOD) mod MOD
mul() 함수를 정의하면, b,
return ((a mod MOD) * (b mod MOD)) mod MOD
주요 방법에서 다음과 같이 -
n :=s
의 크기
크기가 26인 배열 dp를 정의합니다.
해상도 :=0
s :=s 앞에 공백 연결
initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
- x :=s[i]
- 추가됨 :=sub(add(res, 1), dp[x - 'a'])
- dp[x - 'a'] =add(dp[x - 'a'], 추가됨)
- res :=add(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"