mediumBacktrackingPure DSA~25 min
All Palindrome Partitions of a String
A text segmenter splits a token string into pieces that each read the same forwards and backwards. Enumerate every way to fully partition the string into palindromic pieces.
Problem
Given a string s, partition it so that every substring of the partition is a palindrome. Return all possible palindrome partitionings (each as a list of substrings).
Input
A string s of lowercase letters.
Output
A list of partitions, each a list of palindromic substrings.
Constraints
- 1 <= s.length <= 16
- s consists of lowercase English letters.
Examples
Example 1
Input
s = "aab"
Output
[["a","a","b"],["aa","b"]]
Two ways to split into palindromes.
Example 2
Input
s = "a"
Output
[["a"]]
A single character is a palindrome.