इस समस्या में, हमें एक पैलिंड्रोमिक स्ट्रिंग दी जाती है। और हमें इस स्ट्रिंग के सभी पार्टिशन को प्रिंट करना है। इस समस्या में, हम स्ट्रिंग के सभी संभावित पैलिंड्रोम विभाजन को काटकर पाएंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं -
इनपुट - स्ट्रिंग ='अबाबा'
आउटपुट - अबाबा, ए बाब ए, ए बी ए बी ए….
इस समस्या का समाधान यह जांचना है कि कोई सबस्ट्रिंग पैलिंड्रोम है या नहीं। और अगर सबस्ट्रिंग सबस्ट्रिंग है तो उसे प्रिंट करें।
उदाहरण
नीचे दिया गया प्रोग्राम समाधान का वर्णन करेगा -
#include<bits/stdc++.h>
using namespace std;
bool isPalindrome(string str, int low, int high){
while (low < high) {
if (str[low] != str[high])
return false;
low++;
high--;
}
return true;
}
void palindromePartition(vector<vector<string> >&allPart, vector<string> &currPart, int start, int n, string str){
if (start >= n) {
allPart.push_back(currPart);
return;
}
for (int i=start; i<n; i++){
if (isPalindrome(str, start, i)) {
currPart.push_back(str.substr(start, i-start+1));
palindromePartition(allPart, currPart, i+1, n, str);
currPart.pop_back();
}
}
}
void generatePalindromePartitions(string str){
int n = str.length();
vector<vector<string> > partitions;
vector<string> currPart;
palindromePartition(partitions, currPart, 0, n, str);
for (int i=0; i< partitions.size(); i++ ) {
for (int j=0; j<partitions[i].size(); j++)
cout<<partitions[i][j]<<" ";
cout<<endl;
}
}
int main() {
string str = "abaaba";
cout<<"Palindromic partitions are :\n";
generatePalindromePartitions(str);
return 0;
} आउटपुट
Palindromic partitions are : a b a a b a a b a aba a b aa b a a baab a aba a b a aba aba abaaba