print all palindromic partitions

Given a string, write a function that will print all palindromic partitions of a given string

Example

INPUT
s = “bcdcb”

OUTPUT
[‘b’, ‘c’, ‘d’, ‘c’, ‘b’]
[‘b’, “cdc”, ‘b’]
[“bcdcb”]

In this method the main idea is to use vectors, create a 2 dimensional vector to store all the partitions and a 1 dimensional vector to store the current partition

Algorithm

1. Traverse through every substring starting from first charcater

2. If the substring is a palindrome, then add it to the solution

3. recur for the remaining part

C++ Program

#include<bits/stdc++.h>
using namespace std;
 
//function to check if s is palindroem
bool isPalindrome(string s, int start, int end)
{
    while (start < end)
    {
        if (s[start++] != s[end--])
            return false;
    }
    return true;
}
 
//Recursive function,
//sol is a vector of vectors, each vector store a partition
//cPartition is a vector of strings to store current partition
void recAllPPartitions(vector<vector<string> >&sol, vector<string> &cPartition, 
                   int start, int n, string s)
{
    // If 'start' has reached len
    if (start >= n)
    {
        sol.push_back(cPartition);
        return;
    }
 
    // Pick all possible ending points for substrings
    for (int i=start; i<n; i++)
    {
        // If substring s[start..i] is palindrome
        if (isPalindrome(s, start, i))
        {
            // Add the substring to result
            cPartition.push_back(s.substr(start, i-start+1));
 
            // Recur for remaining remaining substring
            recAllPPartitions(sol, cPartition, i+1, n, s);
             
            // Remove substring s[start..i] from current 
            // partition
            cPartition.pop_back();
        }
    }
}
 
// Function to print all possible palindromic partitions of
// s. It mainly creates vectors and calls allPalPartUtil()
void printAllPPartitions(string s)
{
    int n = s.length();
 
    // To Store all palindromic partitions
    vector<vector<string> > sol;
 
    // To store current palindromic partition
    vector<string> cPartition; 
 
    // to generate all partitions
    recAllPPartitions(sol, cPartition, 0, n, s);
 
    // Print all partitions
    for (int i=0; i< sol.size(); i++ )
    {
        cout<<"[ ";
        for (int j=0; j<sol[i].size(); j++)
            cout << sol[i][j] << " ";
        cout<<"]";
        cout <<endl;

    }
}
 
// Driver program
int main()
{
    string s = "bcdcb";
    printAllPPartitions(s);
    return 0;
}

Try It

 

 

Translate »