LeetCode (Python): Palindrome Partitioning

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, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution:

We can use dynamic programming to calculate all the possible substrings if they are palindrome or not and save them in a matrix. Then we use backtracking to generate all the possible partitions.

class Solution:
    # @param s, a string
    # @return a list of lists of string
    def partition(self, s):
        isPalindrome = []
        for start in range(0, len(s)):
            isPalindrome.append([])
            
        for length in range(0, len(s)):
            for start in range(0,len(s)-length):
                if length==0:
                    isPalindrome[start].append(True)
                elif length == 1:
                    isPalindrome[start].append(s[start]==s[start+length])
                else:
                    isPalindrome[start].append(isPalindrome[start+1][length-2] and s[start]==s[start+length])
        
        solution = []
        self.partitionRec(s,0,isPalindrome, [], solution)
        return solution
    
    def partitionRec(self,s,index, isPalindrome, tempSolution, solution):
        if index==len(s):
            solution.append(list(tempSolution))
        
        for length in range(0, len(s)-index):
            if isPalindrome[index][length]:
                tempSolution.append(s[index:index+length+1])
                self.partitionRec(s,index+length+1,isPalindrome, tempSolution, solution)
                tempSolution.pop()