758. Palindrome Partitioning

Given a string s, partition it into substrings such that EVERY substring is a palindrome. Return all possible such partitions. Each partition is a list of strings whose concatenation equals s. The output must be sorted lexicographically as a list of lists of strings.

Input: A string s enclosed in double quotes.

Output: Return a sorted list of partitions, each a list of palindrome strings.

Examples

Input: "aab"
Output: [["a","a","b"],["aa","b"]]
Explanation: Two valid partitions: {a,a,b} and {aa,b}.

Input: "a"
Output: [["a"]]
Explanation: Single character is a palindrome.

Input: "ab"
Output: [["a","b"]]
Explanation: Only the single-character split is all-palindromic.

Constraints

• 1 <= s.length <= 7
• s contains lowercase English letters only

Asked by