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()) {
            result.add(new ArrayList<>(partition));
            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)) {
                partition.add(s.substring(index, i + 1));
                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();
    AddPalindrome(s, 0, partition, result);
 
    return result;
}
 
private void AddPalindrome(string s, int start, List partition, List> result)
{
    //stop condition
    if (start == s.Length)
    {
        List temp = new List(partition);
        result.Add(temp);
        return;
    }
 
    for (int i = start + 1; i <= s.Length; i++)
    {
        string str = s.Substring(start, i - start);
        if (IsPalindrome(str))
        {
            partition.Add(str);
            AddPalindrome(s, i, partition, result);
            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;
}