Palindrome Partitioning - Leetcode Solution

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"]
]

1