দুটি স্ট্রিং S এবং T দেওয়া আছে। S-এর কতগুলো ডিস্টিংট সাবসিকোয়েন্স T-এর সমান তা গণনা করুন। সাবসিকোয়েন্স মানে কিছু অক্ষর বাদ দিয়ে বাকিগুলোর রিলেটিভ অর্ডার রক্ষা করে নতুন স্ট্রিং বানানো।
উদাহরণ: "baalllloonnn" এবং "balloon" -> ৩৬টি উপায়।
সমাধানের ধাপসমূহ
- n = S.size(), m = T.size()। S এবং T-এর শুরুতে স্পেস যোগ করুন (1-বেসড ইন্ডেক্সিং)।
- (n+1) x (m+1) DP টেবিল বানান। dp[0][0] = 1, প্রথম কলাম সব ১।
- i=1 থেকে n, j=1 থেকে m পর্যন্ত:
- যদি S[i] == T[j], dp[i][j] = dp[i-1][j-1]।
- dp[i][j] += dp[i-1][j]।
- dp[n][m] রিটার্ন করুন।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int numDistinct(string s, string t) {
int n = s.size(), m = t.size();
s = " " + s; t = " " + t;
vector<vector<lli>> dp(n+1, vector<lli>(m+1));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) dp[i][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i] == t[j]) dp[i][j] = dp[i-1][j-1];
dp[i][j] += dp[i-1][j];
}
}
return dp[n][m];
}
};
int main() {
Solution ob;
cout << ob.numDistinct("baalllloonnn", "balloon");
return 0;
}
ইনপুট
"baalllloonnn" "balloon"
আউটপুট
36
