力扣刷题笔记：131.分割回文串（回溯经典题，直接套模板）

逃离我推掉我的手 2022-11-06 01:59 100阅读 0赞

## 题目： ##

131、分割回文串

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

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

示例:

> 输入: “aab”  
> 输出:  
> \[  
> \[“aa”,“b”\],  
> \[“a”,“a”,“b”\]  
> \]

## 题解思路： ##

看到题目要求「所有可能的结果」，而不是「结果的个数」，一般情况下，我们就知道需要暴力搜索所有的可行解了，可以用「回溯法」。直接套回溯法python模板代码。

> 回溯法python模板套路：[https://blog.csdn.net/weixin\_44414948/article/details/114489545][https_blog.csdn.net_weixin_44414948_article_details_114489545]

时间复杂度：O(N \* 2 ^ N)，因为总共有 O(2^N) 种分割方法，每次分割都要判断是否回文需要 O(N) 的时间复杂度。  
空间复杂度：O(2 ^ N)，返回结果最多有 O(2 ^ N)种划分方法。

## 题解python代码： ##

Python 解法在每次搜索位置区域的时候，使用的是产生一个新数组 path + \[s\[:i\]\] ，这样好处是方便：不同的路径使用的是不同的 path，因此不需要 path.pop() 操作；而且 res.append(path) 的时候不用深度拷贝一遍 path。

class Solution(object):
        def partition(self, s):
            self.isPalindrome = lambda s : s == s[::-1]
            res = []
            self.backtrack(s, res, [])
            return res
            
        def backtrack(self, s, res, path):
            if not s:
                res.append(path)
                return
            for i in range(1, len(s) + 1): #注意起始和结束位置
                if self.isPalindrome(s[:i]):
                    self.backtrack(s[i:], res, path + [s[:i]])

> 作者：fuxuemingzhu  
> 链接：[https://leetcode-cn.com/problems/palindrome-partitioning/solution/hui-su-fa-si-lu-yu-mo-ban-by-fuxuemingzh-azhz/][https_leetcode-cn.com_problems_palindrome-partitioning_solution_hui-su-fa-si-lu-yu-mo-ban-by-fuxuemingzh-azhz]  
> 来源：力扣（LeetCode）[https://leetcode-cn.com/problems/palindrome-partitioning/][https_leetcode-cn.com_problems_palindrome-partitioning]

[https_blog.csdn.net_weixin_44414948_article_details_114489545]: https://blog.csdn.net/weixin_44414948/article/details/114489545
[https_leetcode-cn.com_problems_palindrome-partitioning_solution_hui-su-fa-si-lu-yu-mo-ban-by-fuxuemingzh-azhz]: https://leetcode-cn.com/problems/palindrome-partitioning/solution/hui-su-fa-si-lu-yu-mo-ban-by-fuxuemingzh-azhz/
[https_leetcode-cn.com_problems_palindrome-partitioning]: https://leetcode-cn.com/problems/palindrome-partitioning/