Split a string into all possible lists of substrings such that every substring is a palindrome.
Problem
Given a string s, return all possible ways to partition it into contiguous substrings so that every substring in the partition is a palindrome.
A partition is represented as a list of strings whose concatenation is exactly s.
You should return every valid partition.
Notes
- A substring is palindromic if it reads the same forward and backward.
- The order of partitions in the output does not matter.
- The same substring can appear multiple times in different partitions if it occurs in different positions.
Input Format
- A single string
s.
Output Format
- Return a list of partitions.
- Each partition is a list of palindromic substrings.
Constraints
1 <= s.length <= 16is typical for this problem family.sconsists of lowercase English letters.- The output can be large because all valid partitions must be enumerated.
Example 1
Input
s = "aab"
Output
[["a","a","b"],["aa","b"]]
Explanation
Both partitions use only palindromic substrings. "a", "aa", and "b" are palindromes.
Example 2
Input
s = "a"
Output
[["a"]]
Explanation
The only partition uses the whole string, which is a palindrome.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.