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

C++ में पेलिंड्रोम सबस्ट्रिंग के बार-बार विलोपन के बाद स्ट्रिंग को हटाने के लिए न्यूनतम चरण


समस्या कथन

एक स्ट्रिंग दी गई है जिसमें केवल पूर्णांक के रूप में वर्ण हैं। हमें इस स्ट्रिंग के सभी वर्णों को न्यूनतम चरणों में हटाना है जहां एक चरण में हम वह सबस्ट्रिंग हटा सकते हैं जो पेलिंड्रोम है। सबस्ट्रिंग हटाने के बाद शेष भाग संयोजित हो जाते हैं।

उदाहरण

यदि इनपुट स्ट्रिंग 3441213 है तो न्यूनतम 2 चरण आवश्यक हैं

  • पहले स्ट्रिंग से 121 हटाएं। अब शेष स्ट्रिंग 3443 है
  • शेष स्ट्रिंग को हटाएं क्योंकि यह पेलिंड्रोम है

एल्गोरिदम

हम इस समस्या को हल करने के लिए डायनामिक प्रोग्रामिंग का उपयोग कर सकते हैं

1. मान लें dp[i][j] सबस्ट्रिंग s[i, j] को हटाने में लगने वाले चरणों की संख्या को दर्शाता है 2. प्रत्येक वर्ण को अकेले या किसी सबस्ट्रिंग के भाग के रूप में हटाया जाएगा इसलिए पहले मामले में हम वर्ण को स्वयं हटाएंगे और सबप्रॉब्लम (i+1, j) को कॉल करेंगे 3. दूसरे मामले में हम वर्तमान वर्ण की दाईं ओर सभी घटनाओं पर पुनरावृति करेंगे, यदि K ऐसी किसी घटना का इंडेक्स है तो समस्या दो सबप्रॉब्लम (i+1, K - 1) और (K+1, j) तक कम हो जाएगी 4. हम इस सबप्रॉब्लम (i+1, K-1) तक पहुंच सकते हैं क्योंकि हम समान वर्ण को हटा सकते हैं और मध्य सबस्ट्रिंग के लिए कॉल कर सकते हैं 5. हमें उस मामले का ध्यान रखने की आवश्यकता है जब पहले दो वर्ण समान हों उस स्थिति में हम सीधे सबप्रॉब्लम (i+2, j) तक कम कर सकते हैं

उदाहरण

#include <bits/stdc++.h> using namespace std; int getMinRequiredSteps(string str) {    int n = str.length();    int dp[n + 1][n + 1];    for (int i = 0; i <= n; i++) {       for (int j = 0; j <= n; j++) {          dp[i][j] = 0;       }    }    for (int len = 1; len <= n; len++) {       for (int i = 0, j = len - 1; j < n; i++, j++) {          if (len == 1)             dp[i][j] = 1;          else {             dp[i][j] = 1 + dp[i + 1][j];             if (str[i] == str[i + 1]) {                dp[i][j] = min(1 + dp[i+ 2][j], dp[i][j]);             }             for (int K = i + 2; K <= j; K++){                if (str[i] == str[K]) {                   dp[i][j] =                   min(dp[i+1][K-1] + dp[K+1][j], dp[i][j]);                }             }          }       }    }    return dp[0][n - 1]; } int main() {    string str = "3441213";    cout << "न्यूनतम आवश्यक चरण: " <<    getMinRequiredSteps(str) << endl;    return 0; }

जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है

आउटपुट

न्यूनतम आवश्यक चरण: 2

  1. - C++ में पूर्णांकों की स्ट्रिंग में 6 से विभाज्य सबस्ट्रिंग्स की संख्या

    हम एक ऐसी समस्या को देखेंगे जिसमें हमें एक पूर्णांक स्ट्रिंग दी गई है और यह निर्धारित करना है कि पूर्णांक प्रारूप में कितने सबस्ट्रिंग्स 6 से विभाज्य हैं। यह ध्यान दिया जाना चाहिए कि इनपुट संख्याओं (पूर्णांकों) से बनी स्ट्रिंग के रूप में है। फिर भी, विभाज्यता जांच केवल पूर्णांक के रूप में की जाएगी

  1. - C++ में स्ट्रिंग में पहला दोहराया गया शब्द ज्ञात करें

    इस समस्या में, हमें अल्पविराम से अलग किए गए शब्दों से युक्त एक स्ट्रिंग str दी गई है। हमारा कार्य स्ट्रिंग में पहला दोहराया गया शब्द ज्ञात करना है। हमें पहला शब्द ढूंढना है दो स्पेस के बीच की स्ट्रिंग जो स्ट्रिंग में दोहराया जाता है। समस्या को समझने के लिए एक उदाहरण लेते हैं, इनपुट : str = C program

  1. C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना

    इस लेख में, आप एक दी गई स्ट्रिंग में बनने वाले सबस्ट्रिंग्स (गैर-खाली) की संख्या निकालने के दृष्टिकोण के बारे में जानेंगे।इनपुट: string = moon आउटपुट: 10 व्याख्या: सबस्ट्रिंग्स हैं m, o, o, n, mo, oo, on, moo, oon और moon। इनपुट: string = yellow आउटपुट: 21समाधान खोजने का दृष्टिकोणमान लें स्ट्रिंग की