Palindrome Partitioning

Patrick Leaton
Published: May 19, 2021, 10:18 p.m.
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 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.

 

The description was taken from https://leetcode.com/problems/palindrome-partitioning/.

Problem Solution

#O(N*2^N) Time, O(N) Space
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        output = []
       
        def is_palindrome(left:int, right:int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
       
        def backtrack(start:int, end:int, combo:list) -> None:
            if start == end:
                output.append(list(combo))
            for i in range(start, end):
                if is_palindrome(start, i):
                    partition = s[start:i+1]
                    combo.append(partition)
                    backtrack(i+1, end, combo)
                    combo.pop()
                 
        backtrack(0, len(s), [])
        return output

Problem Explanation

If we are given a problem that requires us to generate each possible combination of something, that is typically an indication that backtracking can be applied.

Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function.  This allows us to circulate elements into each valid position so that we can generate each valid combination. 

A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, check if a placement is valid, then make the placement.  Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.  

This will allow us to circulate in each character for each digit position.

We will start by initializing our output array.

        output = []

 

Next, we will make just a traditional helper function that takes two index pointers for a string and checks if the given substring range is a valid palindrome by comparing both elements before moving the pointers inward.

        def is_palindrome(left:int, right:int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

Next, we will create our recursive, backtrack function. 

The function will take an index to begin a traversal from, an index to end the traversal at, and a combo list that contains a Depth First Search path's current combo.  In this case, the combo will be a combination of palindrome partitions.

        def backtrack(start:int, end:int, combo:list) -> None:

 

Let's set our base case for our function.

If the start pointer has reached the end pointer, then we have completed a valid partitioning for a combination of palindromes.  If that is the case, then we will append the combination to the output by taking a deep copy so that the list isn't overwritten later.

We will then return from the function.

            if start == end:
                output.append(list(combo))

 

Now we'll start getting into the backtracking logic.

Let's create a loop that will iterate from a given starting index to the last index of the string.

This is how we will split up the scope of each combination through recursion because different function calls will have different starting and ending indices to chop up the input string in different ways.

            for i in range(start, end):

 

The constraint we are looking for here is if we can collect each combination of partitioning a string into palindrome substrings.

To abide by that constraint, we will pass the substring ranging from the current function call's starting index to the index of the current iteration into the function we just built and see if it is a palindrome.

                 if is_palindrome(start, i):

 

If this substring is not a palindrome, we will just continue to the next iteration so that we can expand the substring length by one index and continue trying to get a palindrome substring.

If the substring is a palindrome, we will create a partition from the substring and append the partition to the current path's combo.

                    partition = s[start:i+1]
                    combo.append(partition)

 

We will then recurse the function by incrementing the start value to the current iterator, plus one so that we don't get the same partition inside of a combo.  We will also be passing the same ending index value and our current path's combo.

                    backtrack(i+1, end, combo)

 

After we have shot our DFS yoyo down and it has returned back to us, we will pop the last partition from our combo.

                    combo.pop()

 

The reason we do this is that we want to allow the function to circulate positions for each palindrome partition until we have gathered each unique combination from each valid DFS path. 

LeetCode provides a free illustration and animation of how these paths and circulations would look.

Note: In most backtracking diagrams, if the path is going down then it is a function call.  If the path is going to the right then it is a pop or swap.

 

Once we have our backtrack function built, we just need to make the initial call by passing zero as the starting index number, the length of the string as the excluded ending index number, and an empty array for the initial combo.

        backtrack(0, len(s), [])

After our output that contains each valid combination, we will return it and we're done with this question.

        return output