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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment