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

解题方法

这种求全部组合的问题，一般都是用backtracking + dfs试错的方法来做。我们已经知道如何判断一个 string是否是palindrome,那么就不断地去backtracking去找出所有的组合就好了。

其实类似subsets,只不过这里结果里的每一部分是一个palindrome，所以要加上截取palindrome的部分。

Solution

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        results = []
        self.helper(results, s, [])
        return results


    def helper(self, results, s, curList):
        if not s:
            newList = list(curList)
            results.append(newList)

        for i in range(len(s)):
            if self.isPalindrome(s, i):
                curList.append(s[:i+1])
                self.helper(results, s[i+1:], curList)
                curList.pop()


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

Reference