Palindrome partitioning

Hard

Cut where the prefix is a palindrome

Problem

Partition a string so every substring is a palindrome, and return all possible partitionings.

In simple words

Try every prefix that is a palindrome, then recurse on the rest, backtracking when a cut fails.

The idea

Walk the string choosing a cut point; if the prefix up to that cut is a palindrome, keep it and recurse on the rest, then undo the choice and try a longer prefix. Only palindromic prefixes are ever extended, which is the pruning that keeps this tractable.

The trick

Choose, recurse, un-choose — the shape of every backtracking solution.
Precompute an isPalindrome[i][j] table to make each check O(1).
A partition is complete when the cut point reaches the end of the string.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(2^n * n)spaceO(n)

1f(start, cur):2  if start==n: output cur; return3  for end in start..n-1:4    if s[start..end] is palindrome:5      cur.push(s[start..end]); f(end+1, cur); cur.pop()

Input

array: [0]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: s = "aab"
Output:: [['a', 'a', 'b'], ['aa', 'b']]
Explanation:: Split so every piece is a palindrome.

Example 2

Input:: s = "a"
Output:: [['a']]
Explanation:: A single letter → [[a]].

Example 3

Input:: s = "aa"
Output:: [['a', 'a'], ['aa']]
Explanation:: [[a,a],[aa]] both work.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.