Palindrome Partitioning

Bruteforce builder

Problem

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

Return all possible palindrome partitioning of s.

For example:

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

Thought Process

• Should we have another function "isPalindrome" to check if the given string is a palindrome?

  • Yes. This is key becuase we will check if the substring from an anchor pointer (lets call it buildPointer, which is the beginning of substring we are at) to i is a palindrome, as we only want to recurse on valid palindromes

• When do we append to the solution list?

  • We append to the solution list when our buildPointer equals the length of the string because that means we searched the last index.

• How do we do the actual partioning to see if there are any more substrings that are palindromes?

  • We do the actual partioning by first checking if the current substring is a palindrome. If so, then we append this to the current list then recurse on starting at the next character as the beginning to see if there are any more palindromes starting at this next character. This simulates the partioning of palindromes since we only recurse on valid palindromes.

• It is important that we only recurse on valid palindromes, because this simulates the partitioning action. If we know that the current string we have is a palindrome, then start from the next character to see if this or any substrings starting with this next character) is a palindrome.

• It is also important to remember/note we have an anchor pointer that is the beginning of all the substrings we are checking to see if it is a valid palindrome

Solution

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        soln = []
        self.helper(s, [], 0, soln)
        return soln
    
    def helper(self, s, decomp, startBuild, soln):
        if startBuild == len(s):
            soln.append(list(decomp))
        
        else:
            for i in range(startBuild, len(s)):
                if(self.isPalindrome(s,startBuild, i)):
                    pal = s[startBuild:i+1]
                    decomp.append(pal)
                    self.helper(s, decomp, i+1, soln)
                    decomp.pop()
            
    def isPalindrome(self,s,i,j):
        while i <= j:
            if s[i] != s[j]:
                return False
            i+=1
            j-=1
        return True
        

Key Points

• We are only recursing on valid palindromic substrings

• We have an "anchor" variable that acts as the beginning of all substrings we are exploring. The anchor variable is the start of the substring we are exploring. This is important.

• We are saying "From the anchor pointer (which is the beginning position of substrings we are exploring) to i (the end of the substring we are exploring) is this substring a palindrome? If it is then great! Append it to our current list and explore to see if there are more palindrome partitions beginning at the next character by having the anchor start at the next character in the recusive call."

Time Complexity

• Time: $O(n*2^n)$ because worst case we have is n repetitions (like "aaaa")

• Space: $O(n)$ because if we have n repetitions then this will be the depth of the call stack.