Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में टारगेट के समान अद्वितीय सबसीक्वेंसेस की संख्या ढूंढने का प्रोग्राम


परिचय

मान लीजिए हमारे पास दो लोअरकेस स्ट्रिंग्स s और t हैं, हमें s के उन सबसीक्वेंसेस (subsequences) की संख्या ढूंढनी है जो t के बराबर हैं। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^9 + 7 से मोड करके वापस करें।

तो, यदि इनपुट s = "abbd", t = "bd" है, तो आउटपुट 2 होगा, क्योंकि दो संभावित सबसीक्वेंसेस "bd" हैं:

  • s[1] concatenate s[3]
  • s[2] concatenate s[3]

समाधान दृष्टिकोण

डायनामिक प्रोग्रामिंग का उपयोग करते हुए, table[j] t के पहले j कैरेक्टर्स से मेल खाने वाले सबसीक्वेंसेस की संख्या स्टोर करता है।

उदाहरण कोड

#include <bits/stdc++.h>
using namespace std;

int solve(string s, string t) {
    int m = 1000000007;
    if (t.size() == 0) return 0;
    if (t == s) return 1;
    if (t.size() > s.size()) return 0;
    vector<int> table(t.size() + 1, 0);
    table[0] = 1;
    for (int i = 0; i < s.size(); i++) {
        vector<int> onsave = table;
        for (int j = 0; j < table.size(); j++) {
            if (s[i] == t[j]) {
                table[j + 1] = (table[j + 1] % m + onsave[j] % m) % m;
            }
        }
    }
    return table[t.size()] % m;
}

int main(){
    string s = "abbd", t = "bd";
    cout << (solve(s, t));
    return 0;
}

इनपुट

"abbd", "bd"

आउटपुट

2

निष्कर्ष

यह क्लासिक "Distinct Subsequences" समस्या (LeetCode 115) का O(n×m) DP समाधान है। स्पेस को O(m) तक अनुकूलित किया गया है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।


  1. - C++ में संख्या के सम गुणनखंडों का योग (सरल दृष्टिकोण)

    समस्या विवरण इस खंड में हम देखेंगे कि हम किसी संख्या के सभी सम अभाज्य गुणनखंडों का योग कुशल तरीके से कैसे प्राप्त कर सकते हैं। मान लीजिए एक संख्या n = 480 है, हमें इसके सभी गुणनखंड प्राप्त करने हैं। 480 के अभाज्य गुणनखंड 2, 2, 2, 2, 2, 3, 5 हैं। सभी सम गुणनखंडों का योग 2+2+2+2+2 = 10 है। नियम जब

  1. - C++ में रिकर्सन का उपयोग करके किसी संख्या का फैक्टोरियल खोजने का प्रोग्राम

    एक गैर-ऋणात्मक पूर्णांक n का फैक्टोरियल उन सभी धनात्मक पूर्णांकों का गुणनफल होता है जो n से कम या बराबर होते हैं। उदाहरण के लिए: 4 का फैक्टोरियल 24 है। 4! = 4 * 3 * 2 *1 4! = 24 एक पूर्णांक का फैक्टोरियल रिकर्सिव प्रोग्राम या इटरेटिव प्रोग्राम का उपयोग करके पाया जा सकता है। निम्नलिखित प्रोग्राम एक स

  1. - पायथन में विशिष्ट सबसीक्वेंस की संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें स्ट्रिंग s के विशिष्ट सबसीक्वेंस की संख्या गिननी है। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^9 + 7 मॉड्यूलो वापस करें। उदाहरण के लिए, यदि इनपुट s = bab है, तो आउटपुट 6 होगा क्योंकि 6 अलग-अलग अनुक्रम हैं, ये हैं a, b, ba, ab, bb, abb। हल करने के चरण dp := s