Palindrome Partitioning
Given a string
s, your task is to partition s into substrings such that each substring is a palindrome. Return all possible palindrome partitionings of s in the format of pipe-separated substrings. The order of the partitionings can be arbitrary.A palindrome is a string that reads the same forward and backward.
Input
The input consists of a single string
s (1 ≤ |s| ≤ 16), containing only lowercase English letters.Output
Return a list of all possible palindrome partitionings of
s. Each partitioning should be represented as a string where the substrings are joined with the | symbol. The order of the partitionings in the output list can be arbitrary.Examples
Input | Output |
aab | a|a|b
aa|b |
aba | a|b|a
aba |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB