Palindrome Partitioning

Palindrome Partitioning medium

Description

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.

Examples

> Case 1:
    s = "aab"
    Output: [["a","a","b"], ["aa","b"]]
 
> Case 2:
    s = "a"
    Output: [["a"]]
 
> Case 3:
    s = "abba"
    Output: [["a","b","b","a"], ["a","bb","a"], ["abba"]]

Constraints

1 <= s.length <= 16
s contains only lowercase English letters.

State design

This is the partition shape of backtracking. At every position, we decide where to put the next cut.

Partial solution? path — the palindromic pieces picked so far. Plus a start index.
Complete? When start == len(s) — record path.
Choices? Every end in [start + 1, len(s)].
Legality? s[start..end) must be a palindrome.
Undo? Pop the piece after recursing.

Code — basic version (palindrome check inside the loop)

Optimization — precompute palindrome table

isPalindrome(s, l, r) is O(r - l). Called inside backtracking, the total work can balloon. Precompute a 2D table isPal[l][r] in O(n²) once, then check in O(1).

The DP is the same expand-from-center recurrence: isPal[l][r] = (s[l] == s[r]) AND (r - l < 2 OR isPal[l + 1][r - 1]). Fill in order of increasing length.

The O(n²) precompute is a one-time cost; the backtracking step then runs at maximum speed.

Analysis

Time: O(n × 2^n) — there can be exponentially many partitionings, each O(n) to record.
Space: O(n²) for the precomputed palindrome table, O(n) for recursion.

Same skin

Palindrome Partitioning II — minimum cuts (not all partitions). Becomes 1D DP because the answer is a single number, not a list.
Restore IP Addresses (next problem) — partition into exactly 4 pieces, each a valid octet.
Word Break II — partition into pieces that are all dictionary words.
Decode Ways II — count decodings; partition with conditional piece validity ('1'-'26', plus wildcards).

Word Search Restore IP Addresses