Question
All Palindromic Partitions of a String
You are given a string s. Your task is to divide the string into one or more substrings such that each substring is a palindrome (i.e., it reads the same forward and backward).
You must print all possible ways to partition the string that satisfy this condition.
Each valid partition should list the palindromic substrings in the order they appear in the original string.
Input
The first and only line of input contains string s.
Output
Print each valid palindrome partition on a new line, and within each line, print the substrings of that partition separated by a single space.
Example
Input:
aab
Output:
a a b
aa b
Explanation:
The possible palindrome partitions are ["a","a","b"] and ["aa","b"].
We will match the correct palindrome partitions with the returned palindrome partitions.
Example 2:
Input:
a
Output:
a
Explanation:
The possible palindrome partitions are ["a"]
aab
Output:
a a b
aa b
Explanation:
The possible palindrome partitions are ["a","a","b"] and ["aa","b"].
We will match the correct palindrome partitions with the returned palindrome partitions.
Example 2:
Input:
a
Output:
a
Explanation:
The possible palindrome partitions are ["a"]