Palindrom Partition

Question

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

Return all possible palindrome partitioning of s.

Thoughts

Dynamic Programming loop through all the index, 对每一个index, 如果substring(0, i)是一个palindrome, 就将[:i+1]剥离（[:i]不包括i）, 将[i+1:]传入下一个recursive call, 就像算permutations一样

• partition
• partitionHelper
• isPalindrome

Code

class Solution:
    # @param s, a string
    # @return a list of lists of string
    def __init__(self):
        self.results = []

    def partition(self, s):
        # write your code here
        self.partitionHelper(s, [])
        return self.results

    def partitionHelper(self, s, result):
        if not s:
            """
            have to create to a new list
            otherwise it would change, list is mutable
            """
            x = list(result)
            self.results.append(x)
        for i in range(len(s)):
            if self.isPalindrome(s, i):
                result.append(s[:i+1])
                self.partitionHelper(s[i+1:], result)
                result.pop()

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