พิมพ์ Palindromic Partitions ทั้งหมดของสตริงใน C++

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

ตัวอย่างเพื่อความเข้าใจ

Input - string = 'ababa'
Output - ababa, a bab a, a b a b a ...

วิธีแก้ปัญหาคือตรวจสอบว่า substring เป็น palindrome หรือไม่ และพิมพ์ substring ถ้าเป็น palindrome

โปรแกรมตัวอย่าง

#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