【LeetCode 中等题】61-分割回文串

题目描述：给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]
           

解法1。DP+回溯

class Solution:
    def partition(self, s):
        results = []
        self.dfs(s, [], results)
        return results
    
    def dfs(self, s, stringlist, results):
        if len(s) == 0:
            results.append(stringlist)
            # results.append(list(stringlist))
            return
            
        for i in range(1, len(s) + 1):
            prefix = s[:i]
            if self.is_palindrome(prefix):
                self.dfs(s[i:], stringlist + [prefix], results)
                # stringlist.append(prefix)
                # self.dfs(s[i:], stringlist, results)
                # stringlist.pop()

    def is_palindrome(self, s):
        return s == s[::-1]