131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

Python 解答：
1.回溯+动态规划

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        lens = len(s)
        res = []
        flag = [[False for i in range(lens)] for j in range(lens)]
        for i in range(lens):
            flag[i][i] = True
        for k in range(1, lens):
            for i in range(lens-k):
                if i+1 < i+k-1:
                    flag[i][i+k] = flag[i+1][i+k-1] and (s[i] == s[i+k])
                else:
                    flag[i][i+k] = (s[i] == s[i+k])
        print(flag)
        def backtrace(s, i, temp):
            if i == lens:
                res.append(temp)
                return
            else:
                for j in range(lens-i):
                    if flag[i][i+j]:
                        backtrace(s, i+j+1, temp+[s[i:i+j+1]])
        backtrace(s, 0, [])
        return res