এই সমস্যায়, একটি প্যালিনড্রোমিক স্ট্রিং দেওয়া থাকে। এবং আমাদের এই স্ট্রিংয়ের সব পার্টিশন প্রিন্ট করতে হবে। এই সমস্যায়, আমরা স্ট্রিংটি কাটা দিয়ে সব সম্ভাব্য প্যালিনড্রোম পার্টিশন খুঁজে বের করব।
উদাহরণ দিয়ে বুঝি:
ইনপুট − string = 'ababa'
আউটপুট − ababa, a bab a, a b a b a...
এই সমস্যাটির সমাধান হলো চেক করা একটি সাবস্ট্রিং প্যালিনড্রোম কিনা। এবং সাবস্ট্রিংটি প্যালিনড্রোম হলে প্রিন্ট করা।
C++ উদাহরণ
#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
