C++ प्रोग्रामिंग में विशिष्ट सबसीक्वेंस

समस्या विवरण

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

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

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

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (डायनामिक प्रोग्रामिंग):

• n := s का आकार, m := t का आकार। s और t को उनसे पहले खाली स्थान जोड़कर अपडेट करें
• आकार (n + 1) x (m + 1) का एक मैट्रिक्स बनाएं
• dp[0][0] := 1 सेट करें, फिर सभी पंक्तियों के 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] लौटाएं

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();
        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