Problem: Palindrome Partitioning
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.
A palindrome is a string that reads the same backward as forward.
Example 1:
Input:
s = "aab"
Output:
[
["a", "a", "b"],
["aa", "b"]
]
Explanation: The palindrome partitions of “aab” are:
- “a”, “a”, “b”
- “aa”, “b”
Example 2:
Input:
pythonCopy codes = "a"
Output:
[
["a"]
]
Approach:
The task is to find all possible ways to partition a string such that every substring is a palindrome. We can use backtracking to explore all possible partitions of the string. For each partition, we check if the substring is a palindrome. If it is, we continue exploring further; if it’s not, we prune the search.
Steps:
- Backtracking:
- We will recursively try to partition the string.
- At each position, we will try to cut the string into two parts: a prefix and a suffix.
- If the prefix is a palindrome, we add it to the current partition and recursively attempt to partition the suffix.
- If the suffix is eventually empty, we have found a valid partition.
- Palindrome Check:
- A helper function will be used to check if a substring is a palindrome.
- Base Case:
- If the current substring is empty, we return the current partition as one of the solutions.
Time Complexity:
- Time Complexity: O(2N)O(2^N)O(2N), where NNN is the length of the string. This is because in the worst case, we have to explore all subsets of the string.
- Space Complexity: O(N)O(N)O(N), where NNN is the length of the string. This is the depth of the recursion stack.
Algorithm Implementation
Python Code
def partition(s):
def is_palindrome(sub):
return sub == sub[::-1]
def backtrack(start, path):
if start == len(s):
result.append(path[:]) # Make a copy of path and add it to result
return
for end in range(start + 1, len(s) + 1):
substring = s[start:end]
if is_palindrome(substring):
path.append(substring)
backtrack(end, path)
path.pop() # Backtrack
result = []
backtrack(0, [])
return result
# Example test cases
print(partition("aab"))
print(partition("a"))
C++ Code
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> current;
backtrack(s, 0, current, result);
return result;
}
private:
bool isPalindrome(const string& str) {
int left = 0, right = str.size() - 1;
while (left < right) {
if (str[left] != str[right]) return false;
left++;
right--;
}
return true;
}
void backtrack(const string& s, int start, vector<string>& current, vector<vector<string>>& result) {
if (start == s.size()) {
result.push_back(current);
return;
}
for (int end = start + 1; end <= s.size(); ++end) {
string substring = s.substr(start, end - start);
if (isPalindrome(substring)) {
current.push_back(substring);
backtrack(s, end, current, result);
current.pop_back(); // Backtrack
}
}
}
};
int main() {
Solution solution;
vector<vector<string>> result = solution.partition("aab");
for (const auto& partition : result) {
for (const auto& str : partition) {
cout << str << " ";
}
cout << endl;
}
return 0;
}
Java Code
import java.util.*;
public class PalindromePartitioning {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(String s, int start, List<String> current, List<List<String>> result) {
if (start == s.length()) {
result.add(new ArrayList<>(current));
return;
}
for (int end = start + 1; end <= s.length(); end++) {
String substring = s.substring(start, end);
if (isPalindrome(substring)) {
current.add(substring);
backtrack(s, end, current, result);
current.remove(current.size() - 1); // Backtrack
}
}
}
private boolean isPalindrome(String str) {
int left = 0, right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
PalindromePartitioning solution = new PalindromePartitioning();
List<List<String>> result = solution.partition("aab");
for (List<String> partition : result) {
System.out.println(partition);
}
}
}
C# Code
using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<string>> Partition(string s) {
IList<IList<string>> result = new List<IList<string>>();
Backtrack(s, 0, new List<string>(), result);
return result;
}
private void Backtrack(string s, int start, List<string> current, IList<IList<string>> result) {
if (start == s.Length) {
result.Add(new List<string>(current));
return;
}
for (int end = start + 1; end <= s.Length; end++) {
string substring = s.Substring(start, end - start);
if (IsPalindrome(substring)) {
current.Add(substring);
Backtrack(s, end, current, result);
current.RemoveAt(current.Count - 1); // Backtrack
}
}
}
private bool IsPalindrome(string str) {
int left = 0, right = str.Length - 1;
while (left < right) {
if (str[left] != str[right]) return false;
left++;
right--;
}
return true;
}
public static void Main() {
Solution solution = new Solution();
var result = solution.Partition("aab");
foreach (var partition in result) {
Console.WriteLine(string.Join(" ", partition));
}
}
}
JavaScript Code
function partition(s) {
const result = [];
function backtrack(start, current) {
if (start === s.length) {
result.push([...current]);
return;
}
for (let end = start + 1; end <= s.length; end++) {
let substring = s.slice(start, end);
if (isPalindrome(substring)) {
current.push(substring);
backtrack(end, current);
current.pop(); // Backtrack
}
}
}
function isPalindrome(str) {
let left = 0, right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
}
backtrack(0, []);
return result;
}
// Example usage
console.log(partition("aab"));
Summary of the Approach:
- Backtracking:
- Start from the first character of the string.
- At each position, try every possible substring and check if it’s a palindrome.
- If it is, add it to the current partition and recursively attempt to partition the remaining string.
- If the partition reaches the end of the string, add the current partition to the result.
- Palindrome Check:
- For each substring, check if it reads the same forwards and backwards. This can be done by comparing characters from both ends toward the center.
- Backtrack:
- After exploring one valid partition, backtrack to explore other possibilities.
Time Complexity:
- Time Complexity: The time complexity can be approximated as O(2N)O(2^N)O(2N) because, in the worst case, each character could generate two possibilities (a palindrome partition or not).
- Space Complexity: O(N)O(N)O(N), where
Nis the length of the string, to store the recursion stack and intermediate partitions.