Problem:
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
The Steps for solving this problem can be broken down into the following steps:
- Initialize an empty list called
partitionsto store the final result. - Create a backtracking function
solve(start, partition)that takes in two arguments:start: an integer indicating the starting index of the current substring.partition: a list that stores the current palindrome partition.
- Within the backtracking function, check if the
startindex is equal to the length of the input string. If it is, add a copy of the currentpartitionlist to thepartitionslist and return. - Iterate over the substring from the
startindex to the end of the string. For each iteration, check if the substring is a palindrome using theisPalindrome()function. - If the substring is a palindrome, add it to the
partitionlist, and recursively call thesolve()function with the next index and the updatedpartitionlist. - After the recursive call, remove the last element added to the partition.
- Return the
partitionslist after the backtracking function is completed.
This solution uses a backtracking approach to generate all possible partitions of the string, and check if each partition is a palindrome. If it is, the partition is added to the final result, otherwise it’s discarded. This way we get all possible partitions which are palindrome.
Time Analysis
The time complexity of this algorithm is O(2^n * n) where n is the length of the input string.
The reason for this is that for each character in the input string, we have two choices: either include it in the current partition or not. This leads to a total of 2^n possible partitions, and for each partition, we need to check if it’s a palindrome which takes O(n) time. Therefore the total time complexity is O(2^n * n).
It’s worth noting that, this problem has a well-known polynomial time solution, called Manacher’s algorithm, that can solve this in O(n) time, but the above mentioned solution is a backtracking one which leads to the time complexity mentioned.
class Solution {
public:
bool isPalindrome(string str, int startIndex, int lastIndex){
while(startIndex <= lastIndex){
if(str[startIndex] != str[lastIndex])
return false;
startIndex++;
lastIndex--;
}
return true;
}
void solution(int index, vector<string>& ds, vector<vector<string>>& output, string str){
if(index == str.length()){
output.push_back(ds);
return;
}
for(int i = index; i < str.length(); i++){
if(isPalindrome(str, index, i)){
ds.push_back(str.substr(index, i - index + 1));
solution(i+1, ds, output, str);
ds.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> output;
vector<string> ds;
solution(0, ds, output, s);
return output;
}
};This function takes a string as input and returns the same string after inserting “#” in between characters and also at the start and end of the string. It’s a modified version of the original string to handle even-length palindromes. The p[i] array stores the length of the palindrome centered at the ith position.
The algorithm starts by iterating over the modified string and for each position it checks if it’s within the right boundary of the previous palindrome found. If it is, it uses the information from the previous palindrome to find the length of the new one. If it’s not, it starts expanding around the center to find the new palindrome.
The time complexity of this algorithm is O(n), where n is the length of the input string.
It’s important to notice that, this solution is for finding all palindrome substrings of a given string, it’s not a solution for the problem mentioned in the question, which is to find all possible partitions of a string such that each partition is a palindrome.
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> partitions = new ArrayList<>();
solve(s, 0, new ArrayList<>(), partitions);
return partitions;
}
private void solve(String s, int start, List<String> partition, List<List<String>> partitions) {
if (start == s.length()) {
partitions.add(new ArrayList<>(partition));
return;
}
for (int i = start; i < s.length(); i++) {
if (isPalindrome(s, start, i)) {
partition.add(s.substring(start, i + 1));
solve(s, i + 1, partition, partitions);
partition.remove(partition.size() - 1);
}
}
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) {
return false;
}
}
return true;
}
}
const partition = s => {
const partitions = []
const solve = (start, partition) => {
if (start === s.length) {
partitions.push([...partition])
return
}
for (let i = start; i < s.length; i++) {
if (isPalindrome(s, start, i)) {
partition.push(s.slice(start, i + 1))
solve(i + 1, partition)
partition.pop()
}
}
}
solve(0, [])
return partitions
}
const isPalindrome = (s, start, end) => {
while (start < end) {
if (s[start++] !== s[end--]) {
return false
}
}
return true
}
//First Solution
class Solution:
def checkPalindrome(self, str, startIndex, lastIndex):
while startIndex <= lastIndex:
if str[startIndex] != str[lastIndex]:
return False
startIndex += 1
lastIndex -= 1
return True
def palindromePartition(self, index, ds, output, str):
if index == len(str):
output.append(ds[:])
return
for i in range(index, len(str)):
if self.checkPalindrome(str, index, i):
ds.append(str[index:i+1])
self.palindromePartition(i+1, ds, output, str)
ds.pop()
def partition(self, s: str) -> List[List[str]]:
output = []
ds = []
self.palindromePartition(0, ds, output, s)
return output
//Second Solution
class Solution:
def partition(self, s: str) -> List[List[str]]:
def is_palindrome(string):
return string == string[::-1]
def backtrack(start, partition, partitions):
if start == len(s):
partitions.append(partition)
return
for i in range(start, len(s)):
if is_palindrome(s[start:i+1]):
backtrack(i+1, partition + [s[start:i+1]], partitions)
partitions = []
backtrack(0, [], partitions)
return partitions