Tags: "leetcode", "backtracking", access_time 1-min read

Edit this post on Github

Palindrome Partitioning

Created: August 7, 2019 by [lek-tin]

Last updated: August 7, 2019

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

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

Solution

# Time: O(n*2^n)
# Space: `O(n)`. At any time, only one call stack will be in progress
# For example, in put 'ababaaeqwds', one possible call stack will look like 'aba'->'b'->'aa'->'e'->'q'->'w'->'d'->'s': n space
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        if len(s) == 0 or s == None:
            return []

        results = []
        temp = []
        self.search(0, s, temp, results)
        return results

    def search(self, startIndex, s, temp, results):
        if startIndex == len(s):
            results.append(temp[:])
            return

        for i in range(startIndex, len(s)):
            if self.isPalindrome(s, startIndex, i):
                candidateStr = str(s[startIndex:i+1])
                temp.append(candidateStr)
                self.search(i+1, s, temp, results)
                temp.pop()

    def isPalindrome(self, s, start, end):
        while start < end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True