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
- Backtrack over the end of the first substring: for each palindrome prefix, recurse on the remainder.
- The palindrome test is a two-pointer scan, or a precomputed DP table for O(1) queries.
- Every recursion branch appends one palindrome, so the path is exactly a partitioning.
- 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 ofs[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.