Home » Interview Questions » String Interview Questions » Print all palindromic partitions of a string

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

 

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions