C++ में विशिष्ट उपअनुक्रमों की गणना

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

हम जानते हैं कि किसी स्ट्रिंग का उपअनुक्रम (subsequence) एक नई स्ट्रिंग होती है जो मूल स्ट्रिंग से कुछ कैरेक्टर्स (शून्य भी हो सकते हैं) को हटाकर बनती है, बिना शेष कैरेक्टर्स की सापेक्ष स्थिति को बदले। (जैसे, "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")); 
}

इनपुट

"baalllloonnn" "balloon"

आउटपुट

36