สมมติว่าเรามีสตริง S เราต้องนับจำนวนลำดับย่อยที่แตกต่างกันของ S ผลลัพธ์อาจมีขนาดใหญ่ ดังนั้นเราจะส่งคืนคำตอบ modulo 10^9 + 7
ดังนั้น ถ้าอินพุตเป็นเหมือน "bab" ผลลัพธ์จะเป็น 6 เนื่องจากมี 6 ลำดับที่แตกต่างกัน ซึ่งได้แก่ "a", "b, "ba", "ab", "bb", "abb"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน add() ซึ่งจะใช้เวลา a, b,
-
return ((mod MOD) + (b mod MOD)) mod MOD
-
กำหนดฟังก์ชั่นย่อย () สิ่งนี้จะใช้เวลา a, b,
-
return (((a mod MOD) - (b mod MOD)) + MOD) mod MOD
-
กำหนดฟังก์ชัน mul() ซึ่งจะใช้ a, b,
-
กลับมา ((mod MOD) * (b mod MOD)) mod MOD
-
จากวิธีหลักดังนี้ −
-
n :=ขนาดของ s
-
กำหนดอาร์เรย์ dp ขนาด 26
-
res :=0
-
s :=เชื่อมช่องว่างก่อน s
-
สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -
-
x :=s[i]
-
เพิ่ม :=sub(add(res, 1), dp[x - 'a'])
-
dp[x - 'a'] =เพิ่ม (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
