Distinct Subsequences
advanced
String s, string t'nin kaç farklı alt-dizisini (subsequence) içeriyor?
Örnek: s='rabbbit', t='rabbit' → 3.
İpuçları
- 💡 İpucu 1: dp[i][j] = s[:i] içinde t[:j]'nin kaç farklı subsequence olduğu.
- 💡 İpucu 2: s[i-1] == t[j-1] ise dp[i][j] = dp[i-1][j-1] + dp[i-1][j], değilse dp[i][j] = dp[i-1][j].
- 💡 İpucu 3: 1D DP'ye indirgenebilir (O(n) bellek).
Örnek Test Case'ler
Örnek #1
📥 Input
{"s":"rabbbit","t":"rabbit"}Örnek #2
📥 Input
{"s":"babgbag","t":"bag"}Örnek #3
📥 Input
{"s":"abc","t":"abc"}💡 Kodu çalıştırmak ve gerçek çıktılarını görmek için üye girişi yapıp editöre geçebilirsin.