题目描述
题目描述:
给定一个字符串s,将s分割成一些子串,使每个子串都是回文串。
返回s所有可能的分割方案。
示例:
输入:"aab"
输出:
[
["aa","b"],
["a","a","b"]
]
方法和思路
根据题意可知,
返回所有可能的结果,而不是结果个数,我们可以使用回溯法。
回溯法是采用试错的思想,它尝试用分步的策略去解决一个问题。在分步解决问题的过程中,当它通过尝试,发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。
回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:
1.找到一个可能存在的正确的答案。
2.在尝试了所有可能的分步后发现该问题没有答案。
注:
回溯法是一种算法思想;
遍历是实现回溯法的编程方法。
例如下图所示,即为本文的回溯法思想
我们用指针start尝试着不同位置开始切割字符串,若切出一个回文串,基于新的字符串start,继续往下切,直到start字符串越界
每次基于当前start,可以选择不同i,切出start到i的子串,i代表数组的下标,如图字符串aab的012下标。
如上图第一次切割选择了不同i进行切割,
可以切割出a,aa,aab
1.对于切割出来的a,此时a为回文字符串,则继续切割剩下的ab字符串。
ab字符串中,可以选择切割成a和ab两条切割道路
-若切a,此时切割出来的a为回文字符串,
则继续切割剩下的b字符串,
此时切割出来的b为回文字符串,
则此时存储该条道路切割得到的[a,a,b]
-若切ab,此时切割出来的ab不为回文字符串,
则跳过该选择,不落入递归,不存储。
2.对于切割出来的aa,此时aa为回文字符串,则继续切割剩下的b字符串。
此时切割出来的b为回文字符串,
则此时存储该条道路切割得到的[aa,b]
3.对于切割出来的aab,此时aab不为回文字符串。
则跳过该选择,不落入递归,不存储。
我们用代码表示为:
class Solution:
def partition(self, s: str) -> List[List[str]]:
self.isPalindrome=lambda s:s==s[::-1]
res=[]
self.back(s,res,[])
return res
def back(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.back(s[i:],res,path+[s[:i]])