C++ এ স্বতন্ত্র অনুসৃতি

ধরুন আমাদের স্ট্রিং S এবং T আছে। আমাদেরকে S এর স্বতন্ত্র ক্রম সংখ্যা গণনা করতে হবে যা T এর সমান।

আমরা জানি যে একটি স্ট্রিংয়ের পরবর্তী স্ট্রিং হল একটি নতুন স্ট্রিং যা অবশিষ্ট অক্ষরের আপেক্ষিক অবস্থানগুলিকে বিরক্ত না করে কিছু অক্ষর (কোনটিও হতে পারে না) সরিয়ে দিয়ে মূল স্ট্রিং থেকে গঠিত হয়। (যেমন, "ACE" হল "ABCDE" এর একটি অনুবর্তন যেখানে "AEC" নয়)।

যদি ইনপুট স্ট্রিংগুলি হয় "balllloonnn" এবং "বেলুন", তাহলে নির্বাচন করার 36টি ভিন্ন উপায় থাকবে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=s এর আকার, m :=t এর আকার। তাদের আগে ফাঁকা স্থান সংযুক্ত করে s এবং t আপডেট করুন

• আকারের একটি ম্যাট্রিক্স তৈরি করুন (n + 1) x (m + 1)

• dp[0, 0] :=1 সেট করুন, তারপর সমস্ত সারির 0 তম কলামের জন্য 1 সেট করুন, 1 রাখুন

• আমি 1 থেকে n

  রেঞ্জের মধ্যে

  • 1 থেকে m

    পরিসরে j এর জন্য

    • যদি 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];
   }
};
main(){
   Solution ob;
   cout << (ob.numDistinct("baalllloonnn", "balloon"));
}

ইনপুট

"baalllloonnn"
"balloon"

আউটপুট

36