Palindrome Partitioning
Problem
Given a string s, return all possible palindrome partitioning of s such that every substring of the partition is a palindrome.
- 1 ≤ s.length ≤ 16
- s contains only lowercase English letters
Example
s = "aab"[["a","a","b"],["aa","b"]]The brute-force approach would try all possible partitions of the string and check if each substring is a palindrome, which is exponential and inefficient. The optimal approach uses backtracking to build partitions incrementally, pruning paths early by checking palindrome validity. Starting at index 0, the algorithm tries substrings "a", "aa", and "aab". "a" is a palindrome, so it recurses from index 1. From index 1, it tries "a" and "ab"; "a" is palindrome, recurse from index 2. At index 2, "b" is palindrome, so the partition ["a","a","b"] is added. Backtracking then tries "aa" from index 0, which is palindrome, recurses from index 2, and adds ["aa","b"]. The substring "aab" is not palindrome, so it is skipped. This systematic exploration ensures all valid partitions are found without redundant checks.
Approach
Straightforward Solution
A brute-force approach generates all possible partitions and checks each substring for palindrome validity after the fact. This leads to exponential time complexity with redundant palindrome checks and no pruning.
Core Observation
The problem requires enumerating all partitions of a string where each substring is a palindrome. This naturally forms a decision tree where at each index, the algorithm chooses a substring to include if it is a palindrome, then recurses on the remainder.
Path to Optimal
The key insight is to integrate palindrome checking into the backtracking process, pruning invalid partitions early. By checking palindrome validity on the fly and only recursing on valid substrings, the algorithm avoids exploring invalid branches. The recursive function explores all substrings starting at the current index, appends valid palindromes to the current partition, recurses, and then backtracks by removing the last substring. This approach leverages the problem's optimal substructure and overlapping subproblems, enabling efficient exploration of the solution space.
Optimal Approach
Use a backtracking algorithm that starts at index 0 and tries all substrings s[i:j+1]. For each substring, check if it is a palindrome using a helper function. If it is, append it to the current partition and recurse from j+1. When the recursion index reaches the end of the string, add a copy of the current partition to the results. Backtrack by removing the last substring before trying the next. This approach enumerates all valid palindrome partitions efficiently.
Time
O(N * 2^N)
There are up to 2^(N-1) ways to partition a string of length N, and palindrome checking for each substring takes O(N) in the worst case, leading to O(N * 2^N) complexity.
Space
O(N)
The recursion stack and the current partition list can grow up to O(N) in the worst case, excluding the output list which can be exponentially large.
Pattern Spotlight
Backtracking (State Restoration)
For problems requiring enumeration of all valid partitions or combinations, use backtracking with early pruning by validating partial solutions before recursing, and always restore state after recursion to explore alternative branches.
Solution
| 1 | class Solution:
|
| 2 | def partition(self, s: str) -> list[list[str]]:
|
| 3 | res = []
|
| 4 | part = []
|
| 5 |
|
| 6 | def dfs(i):
|
| 7 | if i >= len(s):
|
| 8 | res.append(part.copy())
|
| 9 | return
|
| 10 |
|
| 11 | for j in range(i, len(s)):
|
| 12 | if self.is_palindrome(s, i, j):
|
| 13 | part.append(s[i:j+1])
|
| 14 | dfs(j + 1)
|
| 15 | part.pop()
|
| 16 |
|
| 17 | dfs(0)
|
| 18 | return res
|
| 19 |
|
| 20 | def is_palindrome(self, s, l, r):
|
| 21 | while l < r:
|
| 22 | if s[l] != s[r]:
|
| 23 | return False
|
| 24 | l, r = l + 1, r - 1
|
| 25 | return True |
| 1 | import java.util.ArrayList; |
| 2 | import java.util.List; |
| 3 | |
| 4 | public class Solution { |
| 5 | public List<List<String>> partition(String s) { |
| 6 | List<List<String>> res = new ArrayList<>(); |
| 7 | List<String> part = new ArrayList<>(); |
| 8 | dfs(s, 0, part, res); |
| 9 | return res; |
| 10 | } |
| 11 | |
| 12 | private void dfs(String s, int i, List<String> part, List<List<String>> res) { |
| 13 | if (i >= s.length()) { |
| 14 | res.add(new ArrayList<>(part)); |
| 15 | return; |
| 16 | } |
| 17 | for (int j = i; j < s.length(); j++) { |
| 18 | if (isPalindrome(s, i, j)) { |
| 19 | part.add(s.substring(i, j + 1)); |
| 20 | dfs(s, j + 1, part, res); |
| 21 | part.remove(part.size() - 1); |
| 22 | } |
| 23 | } |
| 24 | } |
| 25 | |
| 26 | private boolean isPalindrome(String s, int l, int r) { |
| 27 | while (l < r) { |
| 28 | if (s.charAt(l) != s.charAt(r)) { |
| 29 | return false; |
| 30 | } |
| 31 | l++; |
| 32 | r--; |
| 33 | } |
| 34 | return true; |
| 35 | } |
| 36 | } |
| 1 | #include <string> |
| 2 | #include <vector> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | vector<vector<string>> partition(string s) { |
| 9 | vector<vector<string>> res; |
| 10 | vector<string> part; |
| 11 | dfs(s, 0, part, res); |
| 12 | return res; |
| 13 | } |
| 14 | |
| 15 | private: |
| 16 | void dfs(const string& s, int i, vector<string>& part, vector<vector<string>>& res) { |
| 17 | if (i >= (int)s.size()) { |
| 18 | res.push_back(part); |
| 19 | return; |
| 20 | } |
| 21 | for (int j = i; j < (int)s.size(); j++) { |
| 22 | if (isPalindrome(s, i, j)) { |
| 23 | part.push_back(s.substr(i, j - i + 1)); |
| 24 | dfs(s, j + 1, part, res); |
| 25 | part.pop_back(); |
| 26 | } |
| 27 | } |
| 28 | } |
| 29 | |
| 30 | bool isPalindrome(const string& s, int l, int r) { |
| 31 | while (l < r) { |
| 32 | if (s[l] != s[r]) { |
| 33 | return false; |
| 34 | } |
| 35 | l++; |
| 36 | r--; |
| 37 | } |
| 38 | return true; |
| 39 | } |
| 40 | }; |
| 1 | var partition = function(s) { |
| 2 | const res = []; |
| 3 | const part = []; |
| 4 | |
| 5 | function dfs(i) { |
| 6 | if (i >= s.length) { |
| 7 | res.push(part.slice()); |
| 8 | return; |
| 9 | } |
| 10 | for (let j = i; j < s.length; j++) { |
| 11 | if (isPalindrome(s, i, j)) { |
| 12 | part.push(s.substring(i, j + 1)); |
| 13 | dfs(j + 1); |
| 14 | part.pop(); |
| 15 | } |
| 16 | } |
| 17 | } |
| 18 | |
| 19 | function isPalindrome(s, l, r) { |
| 20 | while (l < r) { |
| 21 | if (s[l] !== s[r]) { |
| 22 | return false; |
| 23 | } |
| 24 | l++; |
| 25 | r--; |
| 26 | } |
| 27 | return true; |
| 28 | } |
| 29 | |
| 30 | dfs(0); |
| 31 | return res; |
| 32 | }; |
Step-by-Step Solution
Initialize Result and Current Partition Containers
| 3 | res = []
|
| 4 | part = []
|
Objective
To prepare storage for all valid palindrome partitions and the current working partition during recursion.
Key Insight
The result list accumulates all valid partitions found, while the current partition list tracks the substrings chosen so far in the current recursive path. These two data structures enable the backtracking framework to build and store solutions incrementally.
Interview Quick-Check
Core Logic
The result list stores all valid partitions, while the current partition list represents the current path in the recursion tree.
State & Boundaries
The current partition list is cleared and rebuilt during backtracking to explore all possible partitions.
Explore Substrings and Backtrack on Palindromic Partitions
| 6 | def dfs(i):
|
| 7 | if i >= len(s):
|
| 8 | res.append(part.copy())
|
| 9 | return
|
| 11 | for j in range(i, len(s)):
|
| 12 | if self.is_palindrome(s, i, j):
|
| 13 | part.append(s[i:j+1])
|
| 14 | dfs(j + 1)
|
| 15 | part.pop()
|
| 17 | dfs(0)
|
| 18 | return res
|
Objective
To recursively explore all substrings starting at the current index, append palindromic substrings to the current partition, recurse, and backtrack to explore alternatives.
Key Insight
The recursive function uses the current index to try all substrings s[i:j+1]. For each substring, it checks palindrome validity. If valid, it appends the substring to the current partition and recurses from the next index. Upon returning, it removes the substring to restore state. This 'choose, explore, un-choose' pattern is the essence of backtracking, enabling exhaustive yet efficient exploration of all valid partitions.
Interview Quick-Check
Core Logic
Backtracking explores all partitions by choosing palindromic substrings, recursing, and restoring state to try other options.
State & Boundaries
The base case occurs when the current index reaches the string's end, at which point the current partition is a complete valid solution.
Common Pitfalls & Bugs
Failing to remove the last substring after recursion leads to incorrect partitions and duplicates.
Check Palindrome Validity for Substrings
| 20 | def is_palindrome(self, s, l, r):
|
| 21 | while l < r:
|
| 22 | if s[l] != s[r]:
|
| 23 | return False
|
| 24 | l, r = l + 1, r - 1
|
| 25 | return True |
Objective
To verify whether a substring s[l:r] is a palindrome by comparing characters from both ends inward.
Key Insight
The palindrome check uses two pointers moving inward from the substring's boundaries. If any mismatch occurs, the substring is not a palindrome. This check is efficient and critical for pruning invalid partitions early, preventing unnecessary recursion down invalid paths.
Interview Quick-Check
Core Logic
Two-pointer palindrome check ensures substrings are validated in O(length) time before recursion.
Common Pitfalls & Bugs
Not checking palindrome validity before recursion leads to exploring invalid partitions, increasing time complexity.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
part.pop()Remove the last substring to backtrack and restore state.
This state restoration is the single most critical line in backtracking; it ensures that after exploring one branch, the algorithm can correctly explore others without contamination from previous choices.
res.append(part.copy())Add a copy of the current partition to the results list.
Copying is essential because the current partition list is mutable and will be modified during backtracking; storing a copy preserves the valid solution.
if self.is_palindrome(s, i, j):Check if the substring s[i:j+1] is a palindrome.
This conditional prunes the search space by only exploring partitions that include palindromic substrings, avoiding invalid branches.
if s[l] != s[r]:Return False immediately if characters at pointers do not match.
Early termination upon mismatch prevents unnecessary checks and prunes invalid substrings quickly.
if i >= len(s):Check if the current index has reached the end of the string.
This base case signals that a complete partition has been formed, ready to be added to the results.
returnTerminate the current recursive branch after recording the completed partition so the algorithm can backtrack and explore other possible splits.
Once the recursion reaches the end of the string, the current partition already represents a complete valid decomposition of the entire input. Returning immediately prevents further exploration and allows backtracking to continue exploring alternative partitions.
dfs(j + 1)Recursively explore partitions starting from the next index after the current substring.
This recursive call advances the exploration, building partitions from the remaining substring.
return TrueReturn True if all character pairs matched, confirming palindrome.
If no mismatches were found, the substring is a palindrome, enabling its inclusion in partitions.
for j in range(i, len(s)):Iterate over all possible substring end indices starting from i.
This loop explores every substring starting at index i, enabling exhaustive search of all partition options.
part.append(s[i:j+1])Append the palindromic substring to the current partition.
Adding the substring represents the 'choose' step in backtracking, extending the current solution path.
while l < r:Use two pointers to compare characters from both ends of the substring.
This two-pointer technique efficiently verifies palindrome property by converging inward.
part = []Initialize the current partition list to track substrings in the current recursive path.
This list represents the current state of the partition being built and is modified during recursion and backtracking.
def dfs(i):Define the recursive function to explore partitions starting at index i.
Encapsulating the backtracking logic in a helper function allows clean management of recursion state and parameters.
dfs(0)Initiate the backtracking process from the start of the string.
Starting recursion at index 0 triggers the exploration of all possible palindrome partitions.
def is_palindrome(self, s, l, r):Define the helper function to check if a substring is a palindrome.
Encapsulating palindrome checking in a separate function improves code clarity and reuse.
return FalseMove pointers inward to continue palindrome checking.
Advancing pointers maintains the invariant of checking corresponding characters until pointers cross.
res = []Initialize the list to store all valid palindrome partitions.
This list accumulates the final output, collecting all partitions found during the backtracking process.
return resReturn the list of all palindrome partitions found.
After recursion completes, this returns the accumulated valid partitions to the caller.
Test Your Understanding
Why is it necessary to backtrack (remove the last substring) after each recursive call in this algorithm?
Because the current partition list is shared across recursive calls, removing the last substring restores the state to explore alternative partitions starting from the same prefix, ensuring all valid partitions are found without interference.
Related Problems
Backtracking pattern
Don't just read it. Drill it.
Reconstruct Palindrome Partitioning from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Palindrome Partitioning drill