C++ में पैलिंड्रोम विभाजन (Palindrome Partitioning)

मान लीजिए हमारे पास एक इनपुट स्ट्रिंग है, उस स्ट्रिंग का एक विभाजन पैलिंड्रोम विभाजन है, जब विभाजन का हर उपस्ट्रिंग एक पैलिंड्रोम हो। इस खंड में, हमें दी गई स्ट्रिंग को पैलिंड्रोम विभाजन करने के लिए आवश्यक न्यूनतम कट (minimum cuts) ढूंढने हैं। यदि स्ट्रिंग "ababbbabbababa" है, तो पैलिंड्रोम के रूप में विभाजन के लिए न्यूनतम कट। यहां 3 कट की आवश्यकता है। पैलिंड्रोम हैं: a | babbbab | b | ababa

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• 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] true है, तो 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) का न्यूनतम
• cut[0, n-1] वापस करें

उदाहरण

#include <iostream>
#include <climits>
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 << "पैलिंड्रोम विभाजन के लिए न्यूनतम कट: " << minPalPartion(str);
}

इनपुट

ababbbabbababa

आउटपुट

पैलिंड्रोम विभाजन के लिए न्यूनतम कट: 3