MediumNeetCode150StringBacktracking
Palindrome Partitioning
Return all palindromic partitioning of s.
Examples
Input
s = "aab"
Output
[[a,a,b],[aa,b]]
Two ways to partition.
Constraints
- •
1 <= s.length <= 16 - •
Lowercase English letters
Approaches
Try all partitions.
CodeT: O(2^n) | S: O(n)
Recurse and check palindrome.
CodeT: O(n*2^n) | S: O(n) recursion depth
def partition(s):
r=[]
def bt(i,cur):
if i==len(s): r.append(cur[:]); return
for j in range(i,len(s)):
if s[i:j+1]==s[i:j+1][::-1]:
cur.append(s[i:j+1]); bt(j+1,cur); cur.pop()
bt(0,[]); return rPrecompute palindrome table.
CodeT: O(n*2^n) | S: O(n^2) DP table
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Try all partitions. |
| Backtracking | O(n*2^n) | O(n) recursion depth | Recurse and check palindrome. |
| Backtracking + DP | O(n*2^n) | O(n^2) DP table | Precompute palindrome table. |
Brute Force
T: O(2^n)S: O(n)
Try all partitions.
Backtracking
T: O(n*2^n)S: O(n) recursion depth
Recurse and check palindrome.
Backtracking + DP
T: O(n*2^n)S: O(n^2) DP table
Precompute palindrome table.
Common Mistakes
Not checking palindrome correctly
Not restoring state
Wrong split index