131_ Palindrome Partitioning

[Medium][String, Backtracking]

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:

Idea:

• Focus on the first possible palindromic string in a partition.

  • The first string itself is a valid palindromic partition.

  • Do a linear search to find all the possible palindromic substring starting from the first letter.

• Use recursion to deal with the left over.

Time Complexity: $O(n 2^n)$ according to EPI page 236

Space Complexity: no extra space except for the output

def partition(s):
    """
    :type s: str
    :rtype: List[List[str]]
    """
    def helper(offset, partial):
        # offset is the position of current string we are dealing with
        # partial is the substring that are already partitioned

        if offset == len(s):
            output.append(list(partial))  # list is not neccesary here
            return

        # case when s[offset] is partitioned
        helper(offset+1, partial+[s[offset]])

        # find the next palindrome candidate
        for i in range(offset+1, len(s)):
            if s[i] == s[offset]:
                if s[offset:i+1] == s[offset:i+1][::-1]:
                    helper(i+1, partial+[s[offset:i+1]])

    output = []
    helper(0, [])
    return output