พิมพ์พาร์ทิชันพาลินโดรมทั้งหมดของสตริงใน C++

ในปัญหานี้ เราได้รับสตริงพาลินโดรม และเราต้องพิมพ์พาร์ติชั่นทั้งหมดของสตริงนี้ ในปัญหานี้ เราจะหาพาร์ติชั่นพาลินโดรมที่เป็นไปได้ทั้งหมดของสตริงโดยการตัดมันออก

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน -

ป้อนข้อมูล − สตริง ='อาบาบา'
ผลผลิต − 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