Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:

Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]

題意

找到一個字符串所有可以構(gòu)成回文的字串.

思路

回溯法。首先按一個字符切割，如果是回文，則存入path，再對字串同樣操作，最后將path存入結(jié)果res；再按兩個、三個……字符進(jìn)行判斷。

代碼

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        self.Palindrome = lambda s: s == s[::-1]
        res = []
        self.helper(s, res, [])
        return res

    def helper(self, s, res, path):
        if not s:
            res.append(path)
            return
        for i in range(1, len(s) + 1):
            if self.Palindrome(s[:i]):
                self.helper(s[i:], res, path + [s[:i]])