Interview Notes Search

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.

Building Intuition

Finding All Partitions

The Solution-Space Tree

The Algorithm

Checking for Palindromes

Step-by-Step Walkthrough

Solution

Optimization: Precompute Palindromes