Palindrome Partitioning of a String – LeetCode Problem Solution

12 / 100

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:

  1. Initialize an empty list called partitions to store the final result.
  2. 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.
  3. Within the backtracking function, check if the start index is equal to the length of the input string. If it is, add a copy of the current partition list to the partitions list and return.
  4. Iterate over the substring from the start index to the end of the string. For each iteration, check if the substring is a palindrome using the isPalindrome() function.
  5. If the substring is a palindrome, add it to the partition list, and recursively call the solve() function with the next index and the updated partition list.
  6. After the recursive call, remove the last element added to the partition.
  7. Return the partitions list 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

Leave a Comment