LeetCode 131: Palindrome Partitioning — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Medium — Backtracking | String | Dynamic Programming | Recursion

The Problem

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

Approach

Uses backtracking to explore all possible ways to partition the string. For each position, tries all possible substrings starting from that position, checks if each substring is a palindrome, and recursively partitions the remaining string.

Time: O(N × 2^N) · Space: O(N)

Code

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def is_palindrome(sub):
            return sub == sub[::-1]

        def backtrack(start, partition):
            if start == len(s):
                result.append(partition[:])  # Append a copy of the current partition
                return

            for end in range(start + 1, len(s) + 1):
                sub = s[start:end]
                if is_palindrome(sub):
                    partition.append(sub)
                    backtrack(end, partition)
                    partition.pop()  # Backtrack

        result = []
        backtrack(0, [])
        return result