This page uses the site's newer layout, so only the problem statement and the section outline survive in the public payload — open the original for the rest.
Backtracking
Palindrome Partitioning
medium
DESCRIPTION (inspired by Leetcode.com)
Given a string s, split it into segments where each segment is a palindrome (reads the same forwards and backwards).
Return all possible ways to partition the string into palindromic segments.
Constraints:
-
1 <= s.length <= 16
-
s contains only lowercase English letters
Example 1:
Input:
s = "noon"
Output:
[["n","o","o","n"], ["n","oo","n"], ["noon"]]
Explanation:
-
["n","o","o","n"] - All single characters are palindromes
-
["n","oo","n"] - "oo" is a palindrome in the middle
-
["noon"] - The entire word is a palindrome
Example 2:
Input:
s = "civic"
Output:
[["c","i","v","i","c"], ["c","ivi","c"], ["civic"]]
Example 3:
Input:
s = "aab"
Output:
[["a","a","b"], ["aa","b"]]
The input itself does not need to be a palindrome.