C++ प्रोग्राम: शब्द को पैलिंड्रोम पार्टीशन्स में विभाजित करने के तरीकों की संख्या खोजें

यहां हम एक C++ प्रोग्राम पर चर्चा करेंगे जो एक शब्द को इस तरह पार्टीशन करने के तरीकों की संख्या खोजता है कि प्रत्येक शब्द एक पैलिंड्रोम हो।

एल्गोरिदम

Begin
    शब्द को इनपुट के रूप में लें।
    function partitionadd(vector> &u, string &s, vector &tmp, int index):
        if (index == 0)
            tmp.clear()
        for i = index से length-1 तक
            st = st + s[i]
            if (checkPalin(st))
                tmp.push_back(st)
                if (i+1 < length)
                    partitionadd(u, s, tmp, i+1)
                else
                    u.push_back(tmp)
                tmp = curr
    return
End

function partition(string st, vector> &u):
    vector tmp
    addStrings(u, st, tmp, 0)
    printSol(u) // समाधान प्रिंट करने के लिए
    return
End

उदाहरण

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

bool checkPalin(string s) { // जांचें कि स्ट्रिंग पैलिंड्रोम है या नहीं
    int length = s.length();
    length--;
    for (int i = 0; i < length; i++) {
        if (s[i] != s[length])
            return false;
        length--;
    }
    return true;
}

void printSol(vector> part) { // समाधान प्रिंट करें
    for (int i = 0; i < part.size(); ++i) {
        for(int j = 0; j < part[i].size(); ++j)
            cout << part[i][j] << " ";
        cout << endl;
    }
    return;
}

void partitionadd(vector> &u, string &s, vector &tmp, int index) {
    int length = s.length(); // स्ट्रिंग की लंबाई स्टोर करें
    string st;
    vector curr = tmp;
    
    // सभी इंडेक्स के माध्यम से जाएं और रिकर्सिवली शेष पार्टीशन्स जोड़ें यदि वर्तमान स्ट्रिंग पैलिंड्रोम है
    if (index == 0)
        tmp.clear();
    
    for (int i = index; i < length; ++i) {
        st = st + s[i];
        if (checkPalin(st)) {
            tmp.push_back(st);
            if (i+1 < length)
                partitionadd(u, s, tmp, i+1);
            else
                u.push_back(tmp);
            tmp = curr;
        }
    }
    return;
}

void partition(string st, vector> &u) { // 'str' के सभी पैलिंड्रोमिक पार्टीशन्स जनरेट करें और परिणाम 'm' में स्टोर करें
    vector tmp;
    partitionadd(u, st, tmp, 0); // नोट: मूल कोड में addStrings था जो undefined था
    printSol(u);
    return;
}

int main() {
    string s = "tutorials";
    vector> part;
    cout << "the number of partitions:" << endl;
    partition(s, part);
    return 0;
}

आउटपुट

the number of partitions:
t u t o r i a l s
tut o r i a l s

यह प्रोग्राम बैकट्रैकिंग का उपयोग करके स्ट्रिंग के सभी संभावित पैलिंड्रोमिक पार्टीशन्स ढूंढता है। "tutorials" के लिए, यह दो पार्टीशन्स ढूंढता है: प्रत्येक कैरेक्टर अलग-अलग (सभी सिंगल कैरेक्टर्स पैलिंड्रोम होते हैं) और "tut" + बाकी सिंगल कैरेक्टर्स। ध्यान दें कि मूल कोड में `addStrings` फंक्शन कॉल था जो परिभाषित नहीं था - इसे `partitionadd` होना चाहिए।