Backtracking — Palindrome Partitioning
↗ LeetCode: Palindrome Partitioning · Medium · pattern chapter →
Asked atMetaAmazonGoogleBloomberg
All partitions of s where every part is a palindrome.
Example 1 — s="aab" → [["a","a","b"],["aa","b"]]Example 2 — s="a" → [["a"]]
Constraints — 1 ≤ n ≤ 16. Brute enumerates 2ⁿ⁻¹ cuts, checks each part — O(2ⁿ·n) = 10⁶ ops at n=16. Backtracking with pal[][] cache is O(n·2ⁿ) ≈ 10⁶ ops but skips ~99% via pruning.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — DFS + palindrome check on the fly (canonical)
java
List<List<String>> partition(String s) {
List<List<String>> out = new ArrayList<>();
dfs(s, 0, new ArrayList<>(), out);
return out;
}
void dfs(String s, int start, List<String> path, List<List<String>> out) {
if (start == s.length()) { out.add(new ArrayList<>(path)); return; }
for (int end = start + 1; end <= s.length(); end++) {
if (isPali(s, start, end - 1)) {
path.add(s.substring(start, end));
dfs(s, end, path, out);
path.remove(path.size() - 1);
}
}
}
boolean isPali(String s, int l, int r) {
while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
return true;
}Execution Trace
Step 1 / 3Initialize scan.
Approach 2 — Precompute pal[i][j] DP
O(n²) precompute; O(1) checks during recursion.
Complexity — Time exponential (~2ⁿ · n); Space O(n²) with DP.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| DFS + check | exponential | O(n) | canonical |
| DFS + pal DP | exponential | O(n²) | faster |
When to use which
- Partition into palindromes → DFS + check.
- Min cuts → different problem (see II).
- Count partitions → same skeleton; replace add with count.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems