83. Palindrome Partitioning

Medium · Backtracking

Write a function that partitions a string into all possible ways such that every substring in each partition is a palindrome. A palindrome reads the same forwards and backwards (e.g. 'a', 'aa', 'aba'). Return a list of all valid partitions. Each partition is a list of palindromic substrings that, when concatenated, form the original string. Sort the result lexicographically using JSON.stringify for consistent output.

Examples

Example 1
Input: "aab"
Output: [["a","a","b"],["aa","b"]]
Explanation: Two palindrome partitions

Example 2
Input: "a"
Output: [["a"]]
Explanation: Single-char string

Constraints

• Standard input/output constraints apply