C++ में विशिष्ट परिणाम

मान लीजिए हमारे पास स्ट्रिंग्स एस और टी हैं। हमें एस के अलग-अलग अनुक्रमों की संख्या गिननी है जो टी के बराबर है।

हम जानते हैं कि एक स्ट्रिंग का अनुवर्ती एक नया स्ट्रिंग है जो शेष वर्णों की सापेक्ष स्थिति को परेशान किए बिना वर्णों में से कुछ (कोई नहीं हो सकता) को हटाकर मूल स्ट्रिंग से बनता है। (जैसे, "एसीई" "एबीसीडीई" का अनुवर्ती है जबकि "एईसी" नहीं है)।

अगर इनपुट स्ट्रिंग्स "बैल्लून" और "बैलून" हैं, तो चुनने के 36 अलग-अलग तरीके होंगे।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=s का आकार, m :=t का आकार। s और t को उनके सामने रिक्त स्थान जोड़कर अपडेट करें

• आकार का एक मैट्रिक्स बनाएं (n + 1) x (m + 1)

• dp[0, 0] :=1 सेट करें, फिर सभी पंक्ति के 0वें कॉलम के लिए 1 सेट करें, 1 डालें

• मैं के लिए 1 से n की सीमा में

  • j के लिए 1 से m की सीमा में

    • अगर s[i] =t[j], तो

      • डीपी [आई, जे]:=डीपी [i - 1, जे - 1]

    • डीपी [i, j]:=dp [i, j] + dp [i – 1, j]

• वापसी डीपी [एन, एम]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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