Palindrome Partitioning Problem Statement

Given a string S, the task is to partition S so that every substring in the partition is a palindrome. Return all possible palindrome partitions of S.

Example:

Input:

S = "BaaB"

Output:

[["B", "a", "a", "B"], ["B", "aa", "B"], ["BaaB"]]

Explanation:

Every substring of the partitions such as ["B", "a", "a", "B"], ["B", "aa", "B"], and ["BaaB"] is a palindrome.

Constraints:

0

Question

Palindrome Partitioning Problem Statement

Given a string S, the task is to partition S so that every substring in the partition is a palindrome. Return all possible palindrome partitions of S.

Example:

Input:

S = "BaaB"

Output:

[["B", "a", "a", "B"], ["B", "aa", "B"], ["BaaB"]]

Explanation:

Every substring of the partitions such as ["B", "a", "a", "B"], ["B", "aa", "B"], and ["BaaB"] is a palindrome.

Constraints:

0 <= |S| <= 15 where |S| denotes the length of string S.
Time Limit: 1 sec.

Note:

A substring is a contiguous segment of a string.
All the substrings of a partition are sorted in lexicographical order in the output.
You do not need to print or sort anything, it has already been taken care of. Just implement the function.

Accepted Answer

Given a string, partition it into palindromic substrings and return all possible partitions.

Use backtracking to generate all possible partitions by checking if each substring is a palindrome.
Keep track of the current partition and add it to the result when the entire string is processed.
Optimize by using memoization to store the results of subproblems to avoid redundant calculations.