ধরুন আমাদের কাছে S এবং T দুটি স্ট্রিং আছে। আমাদের কাজ হল S-এর بتلك উপক্রমের (subsequences) সংখ্যা গণনা করা যা T-এর সমান।
আমরা জানি, একটি স্ট্রিং-এর উপক্রম (subsequence) হল একটি নতুন স্ট্রিং যা মূল স্ট্রিং থেকে কিছু অক্ষর (হতে পারে শূন্যও) বাদ দিয়ে, বাকি অক্ষরগুলোর النسبিক অবস্থান অপরিবর্তিত রেখে গঠিত হয়। (যেমন, "ACE" হল "ABCDE"-এর একটি উপক্রম, কিন্তু "AEC" নয়)।
যদি ইনপুট স্ট্রিংগুলো হয় "baalllloonnn" এবং "balloon", তবে ৩৬টি ভিন্ন উপায়ে নির্বাচন করা যাবে।
এই সমস্যাটি সমাধানের জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:
n := S-এর আকার, m := T-এর আকার। S এবং T-এর শুরুতে একটি ব্ল্যাঙ্ক স্পেস যোগ করুন।
(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][j] + dp[i-1][j]
dp[n][m] রিটার্ন করুন।
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বোঝার জন্য:
#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();
int 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
