131-palindrome-partitioning¶

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 string is a string that reads the same backward as forward.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

1 <= s.length <= 16
s contains only lowercase English letters.

Solution(Python)¶

class Solution:
    #  Problem Statement: Given a str s return all possible palindromic
    #  partitions
    #
    #   Input: a string
    #   Output: array of all possible palindromics substring partitions
    #
    #   Example:
    #       1.for s="aaab" return [["a","a","b"],["aa","b"]]
    #
    #   Constraints: 1<= s.length <= 16
    #
    #   Solution:
    #       1.Bruteforce : use backtracking choose a potential candidate (i.e
    #       palindromic substring )from the generated substring from given
    #       constraints
    #
    #       Pseudo code:
    #           fn bactrack (candidate,res,start)
    #               if start reaches end of string
    #                   res.push(cur)
    #
    #               for end=start;end<len(s);end++
    #                   if isPalindrome(s,start,end):
    #                       candidate.push_back(s[start:end+1])
    #                       backtrack(candidate,res,end+1)
    #                       candidate.pop()
    #   Time Complexity: O(N.2^N)
    #   (since our constraint is 1<=n<=16 This is acceptable)
    #   SpaceComplexity: O(n)
    def partition(self, s: str) -> List[List[str]]:
        self.res = []

        @cache
        def isPalindrome(low, high):
            while low < high:
                if s[low] != s[high]:
                    return False
                low += 1
                high -= 1
            return True

        def backtrack(start, cur):
            # candidate selection
            if start >= len(s):
                self.res.append(cur[:])
            # Recursive case
            for end in range(start, len(s)):
                if isPalindrome(start, end):
                    cur.append(s[start: end + 1])
                    backtrack(end + 1, cur)
                    cur.pop()

        backtrack(0, [])
        return self.res