इस समस्या में, हमें एक पैलिंड्रोमिक स्ट्रिंग दी गई है। और हमें इस स्ट्रिंग के सभी विभाजन प्रिंट करने हैं। इस समस्या में, हम स्ट्रिंग को काटकर इसके सभी संभावित पैलिंड्रोम विभाजन ढूंढेंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं -
इनपुट - स्ट्रिंग = 'ababa'
आउटपुट - ababa , a bab a, a b a b a ...
इस समस्या का समाधान यह जांचना है कि कोई उपस्ट्रिंग पैलिंड्रोम है या नहीं। और यदि यह उपस्ट्रिंग है तो उपस्ट्रिंग प्रिंट करें।
उदाहरण
नीचे दिया गया प्रोग्राम समाधान को चित्रित करेगा -
#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
