LeetCode 131: Palindrome Partitioning Solution in Python – A Step-by-Step Guide

What Is LeetCode 131: Palindrome Partitioning?

In LeetCode 131: Palindrome Partitioning, you’re given a string s, and your goal is to return all possible ways to partition it into substrings where each substring is a palindrome. A palindrome is a string that reads the same forward and backward (e.g., "racecar", "aa"). For example, with s = "aab", the output is [["a", "a", "b"], ["aa", "b"]], as both partitions consist entirely of palindromes.

Problem Statement

• Input: A string s.
• Output: A list of lists—each inner list is a valid palindrome partition of s.
• Rules:
• Every substring in a partition must be a palindrome.
• Return all possible partitions.

Constraints

• 1 <= s.length <= 16
• s consists of lowercase English letters.

Examples

• Input: s = "aab"
• Output: [["a", "a", "b"], ["aa", "b"]]
• Why: "a", "a", "b" are palindromes; "aa", "b" are palindromes.
• Input: s = "a"
• Output: [["a"]]
• Why: Single character is a palindrome.
• Input: s = "racecar"
• Output: [["r", "a", "c", "e", "c", "a", "r"], ["r", "aceca", "r"], ["racecar"]]
• Why: Multiple valid partitions, all palindromic.

Understanding the Problem: Carving Palindromes

To solve LeetCode 131: Palindrome Partitioning in Python, we need to generate all possible ways to split the string into palindrome substrings. A naive approach—trying every possible split and checking each—would work but could be slow without optimization, especially with backtracking. We’ll explore:

• Best Solution (Backtracking with Palindrome Check): O(2^n) time, O(n) space—optimized checks.
• Alternative Solution (DP with Backtracking): O(n * 2^n) time, O(n²) space—precomputes palindromes.

Let’s dive into the Best Solution—backtracking with an optimized palindrome check—and break it down step-by-step.

Best Solution: Backtracking with Palindrome Check Optimization

Why This Is the Best Solution

The backtracking approach with an optimized palindrome check is the top pick because it’s efficient—O(2^n) time, O(n) space (recursion stack)—and straightforward, exploring all partitions while pruning non-palindromes early. It builds partitions incrementally, checking each substring’s palindrome property on the fly with a two-pointer method. It’s like slicing the string piece by piece, keeping only the cuts that form palindromes—intuitive and fast for the constraints!

How It Works

Here’s the strategy:

• Step 1: Define Helper Function:
• partition_helper(start, s, current, result): Builds partitions from start index.
• Step 2: Palindrome Check:
• is_palindrome(left, right, s): Two-pointer check for palindrome.
• Step 3: Backtracking:
• For each substring from start to end:
• If palindrome, add to current, recurse, then backtrack.
• Base case: If start reaches end, add current to result.
• Step 4: Start:
• Call helper with empty partition.

Step-by-Step Example

Example: s = "aab"

• Initial Call: partition_helper(0, "aab", [], result).
• start = 0:
• Substring "a" (0,0):
• Palindrome, current = ["a"].
• Recurse: partition_helper(1, "aab", ["a"], result).
• start = 1:
• "a" (1,1):
• Palindrome, current = ["a", "a"].
• Recurse: partition_helper(2, "aab", ["a", "a"], result).
• start = 2:
• "b" (2,2):
• Palindrome, current = ["a", "a", "b"].
• start = 3, add ["a", "a", "b"] to result.
• Backtrack, current = ["a"].
• "ab" (1,2): Not palindrome, skip.
• Backtrack, current = [].
• "aa" (0,1):
• Palindrome, current = ["aa"].
• Recurse: partition_helper(2, "aab", ["aa"], result).
• start = 2:
• "b" (2,2):
• Palindrome, current = ["aa", "b"].
• start = 3, add ["aa", "b"] to result.
• Result: [["a", "a", "b"], ["aa", "b"]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []

        # Step 1: Helper function for backtracking
        def partition_helper(start, s, current, result):
            # Base case: reached end of string
            if start == len(s):
                result.append(current[:])
                return

            # Try all substrings from start
            for end in range(start, len(s)):
                if is_palindrome(start, end, s):
                    current.append(s[start:end + 1])
                    partition_helper(end + 1, s, current, result)
                    current.pop()  # Backtrack

        # Step 2: Palindrome check function
        def is_palindrome(left, right, s):
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        # Step 3: Start backtracking
        partition_helper(0, s, [], result)
        return result

• Line 4: Initialize result list.
• Line 7-16: Backtracking helper:
• Line 9-11: Base case, add partition.
• Line 14-16: Check substring, recurse, backtrack.
• Line 19-25: Palindrome check:
• Line 20-24: Two-pointer comparison.
• Line 28: Start from index 0.
• Time Complexity: O(2^n)—each character can be a cut point or not.
• Space Complexity: O(n)—recursion stack and current list.

This is a palindrome-slicing pro!

Alternative Solution: Dynamic Programming with Backtracking

Why an Alternative Approach?

The DP with backtracking approach precomputes palindrome substrings—O(n * 2^n) time, O(n²) space—then uses backtracking to build partitions. It’s useful for avoiding repeated palindrome checks, trading space for a slight time overhead. It’s like mapping all palindromes first, then assembling the pieces—systematic and thorough!

How It Works

• Step 1: Build DP table for palindromes.
• Step 2: Backtrack using DP table to form partitions.

Step-by-Step Example

Example: s = "aab"

• DP Table (True if palindrome):

a a b a T T F a T F b T

• Backtrack:
• Start 0: "a" (T), recurse 1 → "a" (T), 2 → "b" (T) → ["a", "a", "b"].
• Start 0: "aa" (T), recurse 2 → "b" (T) → ["aa", "b"].
• Result: Same as above.

Code for DP Approach

Copy codeclass Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        # Step 1: Build DP table
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        for length in range(2, n + 1):
            for start in range(n - length + 1):
                end = start + length - 1
                if s[start] == s[end]:
                    if length == 2 or dp[start + 1][end - 1]:
                        dp[start][end] = True

        result = []
        # Step 2: Backtrack with DP
        def backtrack(start, current):
            if start == n:
                result.append(current[:])
                return
            for end in range(start, n):
                if dp[start][end]:
                    current.append(s[start:end + 1])
                    backtrack(end + 1, current)
                    current.pop()

        backtrack(0, [])
        return result

• Line 5-13: Build DP table for palindromes.
• Line 17-25: Backtrack using DP.
• Time Complexity: O(n * 2^n)—DP O(n²), backtracking O(2^n).
• Space Complexity: O(n²)—DP table.

It’s a precomputed palindrome assembler!

Comparing the Two Solutions

• Backtracking (Best):
• Pros: O(2^n) time, O(n) space, simple and fast.
• Cons: Repeated palindrome checks.
• DP with Backtracking (Alternative):
• Pros: O(n * 2^n) time, O(n²) space, precomputed checks.
• Cons: More space, initial overhead.

Backtracking wins for simplicity and space.

Additional Examples and Edge Cases

• "a": [["a"]].
• "aaa": [["a","a","a"], ["a","aa"], ["aa","a"], ["aaa"]].
• "ab": [["a","b"]].

Both handle these perfectly.

Complexity Breakdown

• Backtracking: Time O(2^n), Space O(n).
• DP: Time O(n * 2^n), Space O(n²).

Backtracking’s leaner space shines.

Key Takeaways

• Backtracking: Slice and check!
• DP: Precompute palindromes!
• Partitions: All must be palindromic.
• Python Tip: Lists build fast—see [Python Basics](/python/basics).

Final Thoughts: Carve the String

LeetCode 131: Palindrome Partitioning in Python is a string-slicing adventure. The backtracking approach cuts with elegance, while DP offers a preplanned alternative. Want more palindrome fun? Try LeetCode 5: Longest Palindromic Substring or LeetCode 125: Valid Palindrome. Ready to partition? Head to Solve LeetCode 131 on LeetCode and slice those palindromes today!