Palindrome Partitioning

Problem

Given a string s, split it into a sequence of contiguous non-empty pieces such that every piece is a palindrome. Return every such split. The order of splits in the output does not matter, but the pieces within a split must appear in their original left-to-right order.

• The string is up to 14 characters (short, since the output can be exponential).
• s contains only lowercase English letters.

Examples

• s = "xxy" → [["x","x","y"], ["xx","y"]]. "xxy" itself is not a palindrome, so the first piece is "x" or "xx".
• s = "x" → [["x"]].
• s = "noon" → [["n","o","o","n"], ["n","oo","n"], ["noon"]].

Hints

1. The first piece must be a palindromic prefix. Once you choose it, what is left looks like the original problem.
2. Checking whether s[i..j] is a palindrome inside the recursion repeats the same comparisons many times. Can you answer that in O(1) after some preparation?
3. Backtrack on the start index, trying every palindromic end position; precompute is_pal[i][j] with the interval DP is_pal[i][j] = s[i]==s[j] and is_pal[i+1][j-1].