Leetcode131.分割回文串-Palindrome Patitioning-Python-回溯法

解题思路：

1.切割回文串，可以用解决找组合问题的思路解决，而解决组合问题，可以用回溯法，故本题选择回溯法。

2.理解两个事情：1.递归函数里的for循环是横向遍历给定字符串s的每一个字母。2.针对s的每一个字母，比如在切割了第一个字母之后，还有很多种切割方式，这是由不断的调用递归函数来实现的。

3.判断回文串。用双指针法即可。当然此题也可以用动态规划法，但是为了降低难度，我先不采用这个方法，知识点太多吃不消呀。

注意：

1.判断是回文串之后，如何确定s的索引来将回文串添加至path。因为在判断回文串时，传入的函数参数是startIndex，i。这是确认是否是回文串的索引下标，如果是回文串的话，其实索引startIndex不变，只需要将终止索引+1, 即i+1。例如'aab' startIndex==1, i==2，那么待判断的回文串就是ab.假设ab是回文串，那么索引 startIndex, i+1 就代表着aab的ab。So, do you understand?

            if self.isPalinDrome(s, startIndex, i):self.path.append(s[startIndex:i+1])else:continue

代码：

class Solution(object):result = []path = []def traceBacking(self, s, startIndex):if startIndex >= len(s):self.result.append(self.path[:])returnfor i in range(startIndex, len(s)):if self.isPalinDrome(s, startIndex, i):self.path.append(s[startIndex:i+1])else:continueself.traceBacking(s, i+1)self.path.pop()def isPalinDrome(self,s,startIndex, end):i = startIndexj = endwhile i<j:if s[i] != s[j]:return Falsei +=1j -=1return Truedef partition(self, s):self.result = []self.traceBacking(s, 0)return self.result