Given a string, find all possible palindromic partitions of given string.
Note that this problem is different from Palindrome Partitioning Problem, there the task was to find the partitioning with minimum cuts in input string. Here we need to print all possible partitions.
Example:
Input: nitin
Output: n i t i n
n iti n
nitinInput: neveropen
Output: g e e k s
g ee k s
Brute Force Approach:
The idea is to use recursion and backtracking.
- Partition the string to generate the substrings.
- Check whether the substring generated is palindrome or not.
- If the substring generated is palindrome,
- then add this substring to our current list and recursively call the function for the remaining string.
- When the end of the string is reached the current list is added to the result.
Below is the implementation of above approach.
C++
#include <bits/stdc++.h>using namespace std;class GFG {public: // Check whether the string is palindrom or not. bool checkPalindrome(string& s) { int n = s.size(); int i = 0, j = n - 1; while (i < j) { if (s[i] != s[j]) return false; i++; j--; } return true; } // Recursive function which takes starting index idx // and generates all substrings starting at idx. // If substring generated is palindrome it adds to // current list and makes a recursive call for // remaining string. void Partition(vector<vector<string> >& res, string& s, int idx, vector<string>& curr) { // If we reach the end of string at the current list // to the result. if (idx == s.size()) { res.push_back(curr); return; } // Stores the current substring. string t; for (int i = idx; i < s.size(); i++) { t.push_back(s[i]); // Check whether the string is palindrome is // not. if (checkPalindrome(t)) { // Adds the string to current list curr.push_back(t); // Recursive call for the remaining string Partition(res, s, i + 1, curr); // Remove the string from the current // string. curr.pop_back(); } } }};// Driver codeint main(){ GFG ob; // Stores all the partition vector<vector<string> > res; string s = "neveropen"; // Starting index of string int idx = 0; // Current list vector<string> curr; ob.Partition(res, s, idx, curr); for (auto& v : res) { for (auto& it : v) { cout << it << " "; } cout << "\n"; } return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.ArrayList;class GFG { //funtion to check whether partitioned string is palindrome or not public boolean checkPalindrome(String s) { int n = s.length(); int i = 0; int j = n-1; while(i < j) { if(s.charAt(i) != s.charAt(j)) return false; i++; j--; } return true; } // Recursive funtion which takes index ind and generates all substrings starting at ind. // if substring generated is palindrome it adds to current list and makes a recursive call for remaining string public void partition(ArrayList<ArrayList<String>> res, String s, int ind, ArrayList<String> curr) { // if we reach the end of string // add the current list to the result if(ind == s.length()) { res.add(new ArrayList<String>(curr)); return; } // Store the current substring String temp = ""; for(int i = ind; i < s.length(); i++) { temp += s.charAt(i); // check if string temp is palindrome or not if(checkPalindrome(temp)){ // adds the string to current list curr.add(temp); // Recursive call for the remaining string partition(res, s, i+1, curr); // Remove the string from the current list - (backtracking) curr.remove(curr.size()-1); } } } public static void main(String[] args) { // creating obj of GFG class GFG obj = new GFG(); // Stores all partitions generated at the end ArrayList<ArrayList<String>> res = new ArrayList<>(); String s = "neveropen"; int ind = 0; // Store the partition at current iteration ArrayList<String> curr = new ArrayList<>(); // calling funtion to get partition obj.partition(res, s, ind, curr); for(ArrayList<String> iter : res) { System.out.println(iter); } }} |
C#
using System;using System.Collections.Generic;class GFG { public bool CheckPalindrome(string s) { int n = s.Length; int i = 0, j = n - 1; // Check whether the string is a palindrome while (i < j) { if (s[i] != s[j]) return false; i++; j--; } return true; } public void Partition(List<List<string> > res, string s, int idx, List<string> curr) { // If we reach the end of the string, add the // current list to the result. if (idx == s.Length) { res.Add(new List<string>(curr)); return; } // Stores the current substring. string t = ""; for (int i = idx; i < s.Length; i++) { t += s[i]; // Check whether the string is a palindrome. if (CheckPalindrome(t)) { // Add the string to the current list. curr.Add(t); // Recursive call for the remaining string. Partition(res, s, i + 1, curr); // Remove the string from the current list. curr.RemoveAt(curr.Count - 1); } } } public static void Main(string[] args) { GFG ob = new GFG(); // Stores all the partitions List<List<string> > res = new List<List<string> >(); string s = "neveropen"; // Starting index of the string int idx = 0; // Current list List<string> curr = new List<string>(); ob.Partition(res, s, idx, curr); foreach(var v in res) { foreach(var it in v) { Console.Write(it + " "); } Console.WriteLine(); } }} |
Output
g e e k s g ee k s
Time complexity: O(n*2n), where n is the size of the string. There are 2n possibilities of partitioning the string of length n, and for each possibility, we are checking if the string is a palindrome that costs O(n) time. Hence the overall time complexity is O(n*2n).
Auxiliary Space: O(2n), to store all possible partition of string.
Also read about the Bit Manipulation approach or this problem.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
