Problem Statement: Palindrome Partitioning
Given a string s, partition the string such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Definition:
- A palindrome is a string that reads the same forward and backward (e.g., “madam”, “racecar”).
- A partition of a string divides it into non-empty substrings.
Example:
Example 1:
Input:
plaintextCopy code"aab"
Output:
plaintextCopy code[["a", "a", "b"], ["aa", "b"]]
Explanation: The string “aab” can be split in two ways where each substring is a palindrome:
["a", "a", "b"]: Each character is a palindrome.["aa", "b"]: The first substring “aa” is a palindrome.
Example 2:
Input:
plaintextCopy code"efe"
Output:
plaintextCopy code[["e", "f", "e"], ["efe"]]
Explanation: The string “efe” can be split into:
["e", "f", "e"]: Each character is a palindrome.["efe"]: The entire string is a palindrome.
Approach:
We can solve this problem using backtracking and dynamic programming.
Backtracking Approach:
- Backtracking:
- We will recursively explore all possible partitions of the string.
- At each step, we will try to partition the string into two substrings: one is a palindrome and the other substring is recursively partitioned into palindromes.
- Palindrome Check:
- A helper function will be used to check if a substring is a palindrome.
- Stopping Condition:
- If the entire string has been partitioned and each substring is a palindrome, we will add the partition to the result list.
- Efficiency:
- We avoid checking the same substrings multiple times by using a helper function for palindrome checks, and the recursion ensures that we only generate valid partitions.
Algorithm:
- Use a helper function to check if a substring is a palindrome.
- Use a backtracking approach to try every possible partition of the string.
- If a valid palindrome partition is found, add it to the result list.
- Return the result when the end of the string is reached.
Code Implementation:
1. C++:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool isPalindrome(const string& s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) return false;
start++;
end--;
}
return true;
}
void backtrack(const string& s, int start, vector<string>& current, vector<vector<string>>& result) {
if (start == s.length()) {
result.push_back(current);
return;
}
for (int end = start; end < s.length(); ++end) {
if (isPalindrome(s, start, end)) {
current.push_back(s.substr(start, end - start + 1));
backtrack(s, end + 1, current, result);
current.pop_back(); // backtrack
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> current;
backtrack(s, 0, current, result);
return result;
}
};
int main() {
Solution sol;
string s = "aab";
vector<vector<string>> result = sol.partition(s);
for (const auto& partition : result) {
for (const auto& str : partition) {
cout << str << " ";
}
cout << endl;
}
return 0;
}
2. Java:
import java.util.ArrayList;
import java.util.List;
public 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) {
if (start == s.length()) {
result.add(new ArrayList<>(current));
return;
}
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;
}
public static void main(String[] args) {
Solution sol = new Solution();
String s = "aab";
List<List<String>> result = sol.partition(s);
for (List<String> partition : result) {
for (String str : partition) {
System.out.print(str + " ");
}
System.out.println();
}
}
}
3. Python:
class Solution:
def isPalindrome(self, s, start, end):
while start < end:
if s[start] != s[end]:
return False
start += 1
end -= 1
return True
def backtrack(self, s, start, current, result):
if start == len(s):
result.append(list(current))
return
for end in range(start, len(s)):
if self.isPalindrome(s, start, end):
current.append(s[start:end+1])
self.backtrack(s, end+1, current, result)
current.pop() # backtrack
def partition(self, s):
result = []
self.backtrack(s, 0, [], result)
return result
# Example usage
sol = Solution()
s = "aab"
result = sol.partition(s)
for partition in result:
print(partition)
4. C#:
using System;
using System.Collections.Generic;
public class Solution {
public bool IsPalindrome(string s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) return false;
start++;
end--;
}
return true;
}
public void Backtrack(string s, int start, List<string> current, List<List<string>> result) {
if (start == s.Length) {
result.Add(new List<string>(current));
return;
}
for (int end = start; end < s.Length; ++end) {
if (IsPalindrome(s, start, end)) {
current.Add(s.Substring(start, end - start + 1));
Backtrack(s, end + 1, current, result);
current.RemoveAt(current.Count - 1); // backtrack
}
}
}
public List<List<string>> Partition(string s) {
List<List<string>> result = new List<List<string>>();
List<string> current = new List<string>();
Backtrack(s, 0, current, result);
return result;
}
public static void Main() {
Solution sol = new Solution();
string s = "aab";
List<List<string>> result = sol.Partition(s);
foreach (var partition in result) {
Console.WriteLine(string.Join(" ", partition));
}
}
}
5. JavaScript:
class Solution {
isPalindrome(s, start, end) {
while (start < end) {
if (s[start] !== s[end]) return false;
start++;
end--;
}
return true;
}
backtrack(s, start, current, result) {
if (start === s.length) {
result.push([...current]);
return;
}
for (let end = start; end < s.length; ++end) {
if (this.isPalindrome(s, start, end)) {
current.push(s.substring(start, end + 1));
this.backtrack(s, end + 1, current, result);
current.pop(); // backtrack
}
}
}
partition(s) {
let result = [];
this.backtrack(s, 0, [], result);
return result;
}
}
// Example usage:
let sol = new Solution();
let s = "aab";
let result = sol.partition(s);
result.forEach(partition => {
console.log(partition.join(" "));
});
Time and Space Complexity:
- Time Complexity: The time complexity of this approach is O(2n)O(2^n)O(2n), where nnn is the length of the string. This is because, in the worst case, the recursion explores all possible partitions of the string. Checking if a substring is a palindrome takes O(n)O(n)O(n) time in the worst case, so this doesn’t change the overall complexity significantly.
- Space Complexity: The space complexity is O(n)O(n)O(n), where nnn is the length of the string, due to the recursion stack and the space needed to store the current partition in each recursive call.