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.