131. 分割回文串(中等）-回溯

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

分析

• 回溯，如果不改变原来的变量，也就是不使用引用变量的话，不需要更多操作和撤回的操作
• 有两个变量需要注意，一个是全局的结果，一个是路径跟踪结果
• 还要注意结束条件，这个可以根据具体场景想想，什么时候可以结束
• 判断回文字符串可以通过一个简单的方式s[::-1]

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        # 回溯，如果不改变只是复制变量进行传递，就不用考虑增加和撤销等操作

        def is_palindrome(s):
            return s == s[::-1]
        res = []
        def dfs(path, s):
            # 当字符串为空的时候，就是要返回了
            if not s:
                res.append(path)
                return

            for i in range(1, len(s) + 1):
                if is_palindrome(s[:i]):
                    dfs(path + [s[:i]], s[i:])

        dfs([], s)

        return res