#131
Palindrome Partitioning
Medium Backtracking on cut positions
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Split a string into pieces so that every piece is a palindrome. Return all such splits.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: every way to cut a string into palindrome pieces.
Why this works: choose where the first piece ends (it must be a palindrome), then solve the rest the same way.
Example: "aab"
"a" + "a" + "b""aa" + "b"
✦Hints open one at a time
Choose where the first piece ends; it must be a palindrome.
Then solve the same problem for the rest of the string.
↗Approach
backtrack(start): for each end from start to n − 1, if s[start..end] is a palindrome, add it and recurse from end + 1. Record the path when start reaches n.
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(String s, int start, List<String> path, List<List<String>> res) {
if (start == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int end = start; end < s.length(); end++) {
if (!isPal(s, start, end)) continue;
path.add(s.substring(start, end + 1));
backtrack(s, end + 1, path, res);
path.remove(path.size() - 1);
}
}
private boolean isPal(String s, int l, int r) {
while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
return true;
}
}!Common mistake
Calling substring before checking the palindrome — check with indexes first to avoid making useless strings.
Complexity
- Time: O(n · 2^n).
- Space: O(n).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon