# Solution For Palindrome Partitioning

Problem Description:

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 word, phrase, number, or other sequence of characters that reads the same backward as forward. Examples of palindromes include “racecar” and “level”.

Input: s = “aab”
Output: [[“a”,”a”,”b”],[“aa”,”b”]] Complexity Analysis:

n is the length of the input string s.

Time Complexity: O(2^n) for the worst case when all possible permutations of the string are palindromic. In the average case, the time complexity is around O(n^3), where n is the length of the input string s.

Space Complexity: O(n^2) to store all the possible partitions in the worst case.

Now let’s start developing an optimal solution to the problem.

Solution:

We can use backtracking to find all the possible palindrome partitions of the string.

The approach is to divide the string into all possible substring combinations, and for each substring combination, check if it is palindromic. If it is palindromic, append that substring to the current partition and continue with the rest of the string.

If we reach the end of the string, that means we successfully found a valid partition, so we add that partition to our final result.

Otherwise, we continue dividing the string into more substring combinations until we find all possible palindrome partitions.

Code:

“`
class Solution:
def partition(self, s: str) -> List[List[str]]:
def is_palindrome(s):
return s == s[::-1]

``````    def backtrack(start, partition):
if start == len(s):
result.append(partition.copy())
for end in range(start+1, len(s)+1):
substring = s[start:end]
if is_palindrome(substring):
partition.append(substring)
backtrack(end, partition)
partition.pop()

result = []
backtrack(0, [])
return result
``````

“`

The function “is_palindrome” is used to check whether a given substring is palindromic or not.

The “backtrack” function is the main function to generate all possible palindrome partitions of the string.

The parameter “start” is the starting index of the string from where we will start partitioning the string, and “partition” is the current partition that we are building.

We start with an empty partition and the first index of the string as the starting index.

For each iteration of the “backtrack” function, we try all the possible substring combinations from the “start” index to the end of the string.

If a substring is palindrome, we add it to the current partition, go to the next index, and repeat the process.

If we reach the end of the string, that means we successfully found a valid partition, so we add that partition to our final result.

Otherwise, we continue dividing the string into more substring combinations until we find all possible palindrome partitions.

Finally, we return the final result which contains all possible palindrome partitions of the string.

Example:

Input:

`s = "aab" solution = Solution() print(solution.partition(s))`

Output:

```[ ["a","a","b"], ["aa","b"] ]```

## Step by Step Implementation For Palindrome Partitioning

```public List> partition(String s) {
List> result = new ArrayList<>();
if (s == null || s.length() == 0) {
return result;
}
dfs(s, 0, new ArrayList<>(), result);
return result;
}

private void dfs(String s, int index, List partition, List> result) {
// base case
if (index == s.length()) {
return;
}
// recursive case
for (int i = index; i < s.length(); i++) {
// check if the substring from index to i is a palindrome
if (isPalindrome(s, index, i)) {
dfs(s, i + 1, partition, result);
partition.remove(partition.size() - 1);
}
}
}

private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}```
```def partition(s):
# base case: if string is empty, return empty list
if not s:
return []

# initialize an empty list to store partitions
partitions = []

# loop through each character in the string
for i in range(len(s)):
# if the substring from index 0 to index i is a palindrome
if is_palindrome(s[:i+1]):
# add the substring to the list of partitions
partitions.append(s[:i+1])
# recursively call partition function on the remaining substring
for p in partition(s[i+1:]):
# add the partition to the list of partitions
partitions.append(p)

# return the list of partitions
return partitions

def is_palindrome(s):
# base case: if string is empty, return True
if not s:
return True

# initialize two pointers, one at the beginning and one at the end of the string
left = 0
right = len(s) - 1

# while the left pointer is less than or equal to the right pointer
while left <= right:
# if the characters at the left and right pointers are not equal, return False
if s[left] != s[right]:
return False
# move the left pointer one character to the right
left += 1
# move the right pointer one character to the left
right -= 1

# return True if the string is a palindrome
return True```
```var partition = function(s) {
// create an empty array to store all possible partitions
const partitions = [];

// create a helper function to check if a string is a palindrome
const isPalindrome = (string) => {
// create two pointers, one at the beginning and one at the end of the string
let left = 0;
let right = string.length - 1;

// as long as the pointers haven't crossed, keep checking if the characters at each pointer are equal
while (left < right) {
// if the characters are not equal, the string is not a palindrome, so return false
if (string[left] !== string[right]) {
return false;
}

// if the characters are equal, move both pointers one character to the right/left
left++;
right--;
}

// if the pointers have crossed, the string is a palindrome, so return true
return true;
};

// create a helper function to find all possible partitions for a given string
const findPartitions = (remainingString, currentPartition) => {
// if the remaining string is empty, that means we have found one possible partition
// so we push the current partition into our partitions array
if (remainingString.length === 0) {
partitions.push(currentPartition);
} else {
// otherwise, loop through the remaining string
for (let i = 0; i < remainingString.length; i++) {
// take the substring from the beginning of the remaining string up to the current index
const currentSubstring = remainingString.substring(0, i + 1);

// if the current substring is a palindrome, we add it to the current partition
// and recursively call the helper function with the remaining substring
if (isPalindrome(currentSubstring)) {
const newPartition = [...currentPartition, currentSubstring];
const newRemainingString = remainingString.substring(i + 1);
findPartitions(newRemainingString, newPartition);
}
}
}
};

// call the helper function with the initial inputs
findPartitions(s, []);

// return the array of all possible partitions
return partitions;
};```
```class Solution {
public:
vector> partition(string s) {
vector> res;
vector out;
partitionDFS(s, 0, out, res);
return res;
}
void partitionDFS(string s, int start, vector& out, vector>& res) {
if (start == s.size()) {
res.push_back(out);
return;
}
for (int i = start; i < s.size(); ++i) {
if (isPalindrome(s, start, i)) {
out.push_back(s.substr(start, i - start + 1));
partitionDFS(s, i + 1, out, res);
out.pop_back();
}
}
}
bool isPalindrome(string s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) return false;
++start;
--end;
}
return true;
}
};```
```public IList> Partition(string s)
{
List> result = new List>();

if (string.IsNullOrEmpty(s))
{
return result;
}

List partition = new List();

return result;
}

private void AddPalindrome(string s, int start, List partition, List> result)
{
//stop condition
if (start == s.Length)
{
List temp = new List(partition);
return;
}

for (int i = start + 1; i <= s.Length; i++)
{
string str = s.Substring(start, i - start);
if (IsPalindrome(str))
{
partition.RemoveAt(partition.Count - 1);
}
}
}

private bool IsPalindrome(string str)
{
int left = 0;
int right = str.Length - 1;

while (left < right)
{
if (str[left] != str[right])
{
return false;
}

left++;
right--;
}

return true;
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]