BackTrackingProblem 7 of 19
Print all palindromic partitions of a string
Problem Statement
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Example:
Input: s = "aab"
Output: [["a","a","b"], ["aa","b"]]
Input: s = "nitin"
Output: [["n","i","t","i","n"], ["n","iti","n"], ["nitin"]]
Explanation: Each partition contains only palindromic substrings.
Approach 1: Brute Force (Check Palindrome Each Time)
Intuition
For each position, try all possible substrings starting from that position. If a substring is a palindrome, add it to the current partition and recurse for the remaining string.
Algorithm
- Start from index 0
- Try all substrings from current index to end
- If substring is palindrome, add to current partition and recurse
- When end is reached, add current partition to result
- Backtrack and try longer substrings
java
import java.util.*;
class Solution {
public boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) return false;
start++;
end--;
}
return true;
}
public void backtrack(String s, int start, List<String> current,
List<List<String>> result) {
// Base case: reached end of string
if (start == s.length()) {
result.add(new ArrayList<>(current));
return;
}
// Try all substrings starting from 'start'
for (int end = start; end < s.length(); end++) {
if (isPalindrome(s, start, end)) {
current.add(s.substring(start, end + 1));
backtrack(s, end + 1, current, result);
current.remove(current.size() - 1); // Backtrack
}
}
}
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
List<String> current = new ArrayList<>();
backtrack(s, 0, current, result);
return result;
}
}Complexity Analysis
- Time Complexity: O(n × 2^n) - 2^n partitions, O(n) palindrome check each
- Space Complexity: O(n) - Recursion depth
Approach 2: Optimal (DP Precomputation)
Intuition
Pre-compute which substrings are palindromes using dynamic programming. This reduces palindrome check from O(n) to O(1).
Algorithm
- Build a DP table where dp[i][j] = true if s[i..j] is palindrome
- Use this table in backtracking for O(1) palindrome checks
- dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
java
import java.util.*;
class Solution {
public void backtrack(String s, int start, List<String> current,
List<List<String>> result, boolean[][] dp) {
if (start == s.length()) {
result.add(new ArrayList<>(current));
return;
}
for (int end = start; end < s.length(); end++) {
if (dp[start][end]) {
current.add(s.substring(start, end + 1));
backtrack(s, end + 1, current, result, dp);
current.remove(current.size() - 1);
}
}
}
public List<List<String>> partition(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
// Build palindrome DP table
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (i == j) {
dp[i][j] = true;
} else if (j == i + 1) {
dp[i][j] = (s.charAt(i) == s.charAt(j));
} else {
dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];
}
}
}
List<List<String>> result = new ArrayList<>();
List<String> current = new ArrayList<>();
backtrack(s, 0, current, result, dp);
return result;
}
}Complexity Analysis
- Time Complexity: O(n × 2^n) - 2^n partitions, but O(1) palindrome check
- Space Complexity: O(n²) - For DP table
Approach 3: Expand Around Center (Alternative)
Intuition
Build palindrome information by expanding around each center. This can be more intuitive for some problems.
java
import java.util.*;
class Solution {
public List<List<String>> partition(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
// All single characters are palindromes
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// Expand from each center
for (int center = 0; center < n; center++) {
// Odd length palindromes
int left = center, right = center;
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
dp[left][right] = true;
left--;
right++;
}
// Even length palindromes
left = center;
right = center + 1;
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
dp[left][right] = true;
left--;
right++;
}
}
List<List<String>> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result, dp);
return result;
}
private void backtrack(String s, int start, List<String> current,
List<List<String>> result, boolean[][] dp) {
if (start == s.length()) {
result.add(new ArrayList<>(current));
return;
}
for (int end = start; end < s.length(); end++) {
if (dp[start][end]) {
current.add(s.substring(start, end + 1));
backtrack(s, end + 1, current, result, dp);
current.remove(current.size() - 1);
}
}
}
}Complexity Analysis
- Time Complexity: O(n × 2^n) - Same as DP approach
- Space Complexity: O(n²) - For DP table
Key Takeaways
- DP Optimization: Precompute palindrome info for O(1) checks
- Palindrome DP: dp[i][j] depends on dp[i+1][j-1]
- Partitioning: Try all valid partitions using backtracking
- LeetCode #131: Palindrome Partitioning - Medium difficulty
- Expand Around Center: Alternative to DP for palindrome detection
- Total Partitions: Can be up to 2^(n-1) partitions for a string of length n