[Leetcode] 131. Palindrome Partitioning

Well, doing leetcode problems can be addictive - I used to go to Facebook everyday - not any more and I don't feel missed at all. Now, somehow I must do some leetcode problems, otherwise I just feel wrong. It sometimes gets hard and frustrating. But I guess as I read it somewhere, in our nature human beings just love something bitter, like beer, coffee, as well as challenges (but have to be meaningful and able to make progress and intellectually fulfilling, at least for me).

---

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"]
]

This problem is similar to subset problem, my solution is not the "optimal" one, but very intuitive.

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        if len(s) == 0: return [[]]
        if len(s) == 1: return [[s]]
        
        res = []
        for i in range(1, len(s)+1):
            part1 = s[:i]
            part2 = s[i:]
            #print part1, part2
            if part1 == part1[::-1]:
                tmp_res = self.partition(part2)
                #print tmp_res
                for r in tmp_res:
                    res.append([part1] + r)
        return res