Palindrome Partitioning
You are given a string 'S'. Your task is to partition 'S' such that every substring of the partition is a palindrome. You need to return all possible palindrome partitioning of 'S'.

Note: A substring is a contiguous segment of a string.

For Example:

For a given string “BaaB” 3 possible palindrome partitioning of the given string are: {“B”, “a”, “a”, “B”} {“B”, “aa”, “B”} {“BaaB”} Every substring of all the above partitions of “BaaB” is a palindrome.

Input Format:

The only line of input contains a string 'S'.

Output Format :

For each test case, print all the possible palindromic partitions of the given string in a separate line. Each substring of a partition is written within quotes(““) and separated by comma(,) and space, and each partition of the given string is written inside square brackets[]. The output of each test case will be printed in a separate line.

Note:

All the substrings of a partition are sorted in lexicographical order in the output. You just need to return the partitions in any order. You do not need to print or sort anything, it has already been taken care of. Just implement the function.

Constraints :

0

Question

Palindrome Partitioning

You are given a string 'S'. Your task is to partition 'S' such that every substring of the partition is a palindrome. You need to return all possible palindrome partitioning of 'S'.

Note: A substring is a contiguous segment of a string.

For Example:

For a given string “BaaB”
3 possible palindrome partitioning of the given string are:
{“B”, “a”, “a”, “B”}
{“B”, “aa”, “B”}
{“BaaB”}
Every substring of all the above partitions of “BaaB” is a palindrome.

Input Format:

The only line of input contains a string 'S'.

Output Format :

For each test case, print all the possible palindromic partitions of the given string in a separate line.

Each substring of a partition is written within quotes(““) and separated by comma(,) and space, and each partition of the given string is written inside square brackets[].

The output of each test case will be printed in a separate line.

Note:

All the substrings of a partition are sorted in lexicographical order in the output. You just need to return the partitions in any order.

You do not need to print or sort anything, it has already been taken care of. Just implement the function.

Constraints :

0 <= |S|<= 15
where |S| denotes the length of string 'S'.

Time Limit: 1 sec.

Accepted Answer

Backtracking with Dynamic Programming

We are iterating each time to check whether a given substring is palindrome or not and there we are iterating the same substring of string again and again. So there are overlapping subproblems.
So we use dynamic programming. To overcome the overlapping subproblems we can initially create the DP table which stores if substring[i….j] is palindrome or not. We maintain a boolean dp[N][N] that is filled in a bottom-up manner. The value of dp[i][j] is true if the substring is a palindrome, otherwise false.
To calculate dp[i][j], we first check the value of dp[i+1][j-1], if the value is true and S[i] is the same as S[j], then we make dp[i][j] true. Otherwise, the value of dp[i][j] is made false.
Now to check if the substring is palindrome or not we only check if dp[start][k] is true or not in the recursion. And the rest of the algorithm is the same as the previous approach to generate all possible substrings.

Space Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the length of the string.

In the worst case, we will create a dp array of N * N dimensions thus O(N ^ 2) and also extra space is required for the recursion stack.

Time Complexity: OtherExplanation:

O(N * 2 ^ N), where ‘N’ is the length of the String.

In the worst case, filling the dp takes O(N * N) initially and when all substrings are palindromes then there will be 2 ^ N possible substrings. For each possible substring, it takes O(N) to generate the substring and to check if it is palindrome it takes constant time. Hence the overall complexity will be O(N * 2 ^ N).