Given a string s, split it into pieces so that every piece is a palindrome (reads the same forwards and backwards). Return every possible way to do such a split. Each split is a list of pieces in their original order; the list of splits may be in any order.
- 1 <= s.length <= 16
- s contains only lowercase English letters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries all 2^(n-1) ways to place cuts and checks every piece, paying O(n) per check. Backtracking builds the split from left to right and only continues when the piece just cut off is a palindrome, so impossible branches are cut early. Checking palindromes repeatedly is the remaining cost, and a DP table isPal[i][j] computed once in O(n^2) makes every check constant time.
Algorithm
- Build
isPal[i][j]: true whens[i] == s[j]and (j - i < 2orisPal[i+1][j-1]). Fill it withigoing from right to left. - Define
backtrack(start, path). Ifstart == n, record a copy ofpath. - For each
endfromstartton - 1, ifisPal[start][end], appends[start..end], recurse fromend + 1, then remove it.
O(n * 2^n)Space: O(n^2) for the tableclass Solution: def partition(self, s: str) -> List[List[str]]: n = len(s) # is_pal[i][j] is True when s[i..j] is a palindrome is_pal = [[False] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(i, n): is_pal[i][j] = s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1])ย res, path = [], []ย def backtrack(start): if start == n: res.append(path[:]) return for end in range(start, n): if is_pal[start][end]: path.append(s[start:end + 1]) backtrack(end + 1) path.pop()ย backtrack(0) return res