Print all palindromic partitions of a string

Given a string, write  a function to print all possible palindromic patitioning of s

Example

INPUT
s = "bcc"

OUTPUT
[["b", "c", "c"],  ["b", "cc"]]

Algorithm

1. Maintain two vectors, a 2D vector to store all the possible partitions and a temporory vector for storing the current partition

2. Increamentally check all substrings starting from index i for being palindromic. If found, recursively find for the remaining string and add this to our solution

C++ Program

#include <bits/stdc++.h>
using namespace std;
 
//checks whether the string is palindrome or not
bool isPalindrome(string str)
{
    int n = str.length();
    n--;
    for (int i=0; i<n; i++)
    {
        if (str[i] != str[n])
            return false;
        n--;
    }
    return true;
}
 
void printPartitions(vector<vector<string> > partitions)
{
    for (int i = 0; i < partitions.size(); ++i)
    {
        for(int j = 0; j < partitions[i].size(); ++j)
            cout << partitions[i][j] << " ";
        cout << endl;
    }
    return;
}
 
// Goes through all indexes and recursively add remaining
// partitions if current string is palindrome.
void addStrings(vector<vector<string> > &sol, string &s,
                vector<string> &temp, int index)
{
    int n = s.length();
    string str;
    vector<string> current = temp;
    if (index == 0)
        temp.clear();
    for (int i = index; i < n; ++i)
    {
        str = str + s[i];
        if (isPalindrome(str))
        {
            temp.push_back(str);
            if (i+1 < n)
                addStrings(sol,s,temp,i+1);
            else
                sol.push_back(temp);
            temp = current;
        }
    }
    return;
}
 
//stores all solutions in sol
void allPartitions(string s, vector<vector<string> >&sol)
{
    vector<string> temp;
    addStrings(sol, s, temp, 0);
    printPartitions(sol);
    return;
}
 

int main()
{
    string s = "bcc";
    vector<vector<string> > partitions;
    allPartitions(s, partitions);
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top