⚡Flashcard Drill➔
NeetCode #498LC-131MediumBacktrackingNC 150NC 250
← Back to All Problems

#498 · #131 · Palindrome Partitioning(分割回文串)

📌 Problem Statement & Constraints

Given a string s, partition it so that every substring is a palindrome. Return all possible partitionings. Constraints: 1 <= s.length <= 16.

💡 Core Algorithmic Approaches

  1. Backtrack over the end of the first substring: for each palindrome prefix, recurse on the remainder.
  2. The palindrome test is a two-pointer scan, or a precomputed DP table for O(1) queries.
  3. Every recursion branch appends one palindrome, so the path is exactly a partitioning.
  4. The answer is recorded when the start index reaches the end of the string.

💻 Benchmark Python3 Implementation

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []

        def is_pal(lo: int, hi: int) -> bool:
            while lo < hi:
                if s[lo] != s[hi]:
                    return False
                lo += 1
                hi -= 1
            return True

        def dfs(start: int, path: List[str]) -> None:
            if start == len(s):
                res.append(path[:])        # complete partitioning
                return
            for end in range(start, len(s)):
                if is_pal(start, end):     # only palindromic prefixes branch
                    path.append(s[start:end + 1])
                    dfs(end + 1, path)
                    path.pop()

        dfs(0, [])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * 2^n): there are up to 2^(n-1) partitionings and each palindrome test is O(n). A DP table for the palindrome test would remove the O(n) factor.
💾 Space Complexity
O(n) for the recursion path.

⚠️ Interview Pitfalls & Follow-ups

  • Testing the palindrome after recursing: the branch should only be taken for a valid palindrome prefix.
  • Forgetting path.pop(): the path would accumulate across branches.
  • Assuming a single-character substring is not a palindrome: it always is, which the two-pointer test handles.
  • Using s[start:end] instead of s[start:end+1]: the end index is exclusive, so the substring would be off by one.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems