Palindrome Partitioning

Problem: Palindrome Partitioning

We can use recursion to implement backtracking method to solve this problem. The general idea is to first check the string itself, then iterate divide string into 2 substrings, check these 2 substring and thus recursion.

Code in Python:

class Solution(object):

    def palPart(self, s, pos):
        result = []
        if s[pos:] == s[:pos:-1]+s[pos]:
            result.append([s[pos:]])

        for i in xrange(pos, len(s)):
            if i == len(s) - 1:
                break

            if s[pos:i+1] == s[i:pos:-1]+s[pos]:
                head = [s[pos:i+1]]
                for p in self.palPart(s, i+1):
                    result.append(head + p)

        return result


    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        return self.palPart(s, 0)