परिचय
मान लीजिए हमारे पास दो लोअरकेस स्ट्रिंग्स s और t हैं, हमें s के उन सबसीक्वेंसेस (subsequences) की संख्या ढूंढनी है जो t के बराबर हैं। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^9 + 7 से मोड करके वापस करें।
तो, यदि इनपुट s = "abbd", t = "bd" है, तो आउटपुट 2 होगा, क्योंकि दो संभावित सबसीक्वेंसेस "bd" हैं:
- s[1] concatenate s[3]
- s[2] concatenate s[3]
समाधान दृष्टिकोण
डायनामिक प्रोग्रामिंग का उपयोग करते हुए, table[j] t के पहले j कैरेक्टर्स से मेल खाने वाले सबसीक्वेंसेस की संख्या स्टोर करता है।
उदाहरण कोड
#include <bits/stdc++.h>
using namespace std;
int solve(string s, string t) {
int m = 1000000007;
if (t.size() == 0) return 0;
if (t == s) return 1;
if (t.size() > s.size()) return 0;
vector<int> table(t.size() + 1, 0);
table[0] = 1;
for (int i = 0; i < s.size(); i++) {
vector<int> onsave = table;
for (int j = 0; j < table.size(); j++) {
if (s[i] == t[j]) {
table[j + 1] = (table[j + 1] % m + onsave[j] % m) % m;
}
}
}
return table[t.size()] % m;
}
int main(){
string s = "abbd", t = "bd";
cout << (solve(s, t));
return 0;
}
इनपुट
"abbd", "bd"
आउटपुट
2
निष्कर्ष
यह क्लासिक "Distinct Subsequences" समस्या (LeetCode 115) का O(n×m) DP समाधान है। स्पेस को O(m) तक अनुकूलित किया गया है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।