पैलिंड्रोम पार्टीशनिंग

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

इस एल्गोरिदम में, हमें दी गई स्ट्रिंग को पैलिंड्रोम पार्टीशन करने के लिए आवश्यक न्यूनतम कट्स ढूंढने हैं।

इनपुट और आउटपुट

इनपुट: एक स्ट्रिंग। मान लें "ababbbabbababa"
आउटपुट: पैलिंड्रोम के रूप में पार्टीशन करने के लिए न्यूनतम कट। यहां 3 कट्स की आवश्यकता है।
पैलिंड्रोम हैं: a | babbbab | b | ababa

एल्गोरिदम

minPalPart(str)

इनपुट: दी गई स्ट्रिंग
आउटपुट: स्ट्रिंग से पैलिंड्रोमिक पार्टीशनिंग की न्यूनतम संख्या

शुरुआत
    n := str की लंबाई
    cut मैट्रिक्स और pal मैट्रिक्स प्रत्येक n x n ऑर्डर के परिभाषित करें
    i := 0 से n तक, करें
        pal[i, i] := true
        cut[i, i] := 0
    पूर्ण
    len रेंज 2 से n में, करें
        i रेंज 0 से n - len में, करें
            j := i + len - 1
            यदि len = 2, तो
                यदि str[i] = str[j]
                    pal[i, j] := true
            अन्यथा
                यदि str[i] = str[j] और pal[i+1, j-1] ≠ 0
                    pal[i, j] := true
            यदि pal[i, j] सत्य है, तो
                cut[i, j] := 0
            अन्यथा
                cut[i, j] := ∞
                k रेंज i से j-1 में, करें
                    cut[i, j] := cut[i, j] और (cut[i, k] + cut[k+1, j+1] + 1) का न्यूनतम
                पूर्ण
        पूर्ण
    पूर्ण
    वापस cut[0, n-1]
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

int min(int a, int b) {
    return (a < b) ? a : b;
}

int minPalPartion(string str) {
    int n = str.size();
    int cut[n][n];
    bool pal[n][n];
    
    for (int i = 0; i < n; i++) {
        pal[i][i] = true;
        cut[i][i] = 0;
    }
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n-len+1; i++) {
            int j = i + len - 1;
            if (len == 2)
                pal[i][j] = (str[i] == str[j]);
            else
                pal[i][j] = (str[i] == str[j]) && pal[i+1][j-1];
            
            if (pal[i][j] == true)
                cut[i][j] = 0;
            else {
                cut[i][j] = INT_MAX;
                for (int k = i; k <= j-1; k++)
                    cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j] + 1);
            }
        }
    }
    return cut[0][n-1];
}

int main() {
    string str = "ababbbabbababa";
    cout << "Min cuts for Palindrome Partitioning is: " << minPalPartion(str);
}

आउटपुट

Min cuts for Palindrome Partitioning is: 3