179 - 131 分割回文串

题目

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

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

解答

感觉可以回溯。算出结果，然后验证下是不是回文

https://leetcode-cn.com/problems/palindrome-partitioning/solution/dong-tai-gui-hua-dfs-by-powcai/

方法还是需要两个变量：剩余选择+已走路径

image-20191221095220049

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []

        def backtrack(s, tmp): # s是剩余选择，tmp是已走路径
            if not s:          # 没有选择了，就推进结果里面
                res.append(tmp)
                return
            for i in range(1, len(s)+1):
                if s[:i] == s[:i][::-1]:   # 就是判断s[:i]是不是回文，[::-1]查了才知道还能这么玩，这下都不用回滚选择了。。
                    backtrack(s[i:], tmp+[s[:i]])

        backtrack(s, []) # 两个变量都是通过参数传递，就不用新建
        return res

Runtime: 80 ms, faster than 79.14% of Python3 online submissions for Palindrome Partitioning.

Memory Usage: 13 MB, less than 100.00% of Python3 online submissions for Palindrome Partitioning.