营销的网站,html代码特效,小视频制作软件app,山东省建设注册执业中心网站解题思路#xff1a;
1.切割回文串#xff0c;可以用解决找组合问题的思路解决#xff0c;而解决组合问题#xff0c;可以用回溯法#xff0c;故本题选择回溯法。
2.理解两个事情#xff1a;1.递归函数里的for循环是横向遍历给定字符串s的每一个字母。2.针对s的每一个字…解题思路
1.切割回文串可以用解决找组合问题的思路解决而解决组合问题可以用回溯法故本题选择回溯法。
2.理解两个事情1.递归函数里的for循环是横向遍历给定字符串s的每一个字母。2.针对s的每一个字母比如在切割了第一个字母之后还有很多种切割方式这是由不断的调用递归函数来实现的。
3.判断回文串。用双指针法即可。当然此题也可以用动态规划法但是为了降低难度我先不采用这个方法知识点太多吃不消呀。
注意
1.判断是回文串之后如何确定s的索引来将回文串添加至path。因为在判断回文串时传入的函数参数是startIndexi。这是确认是否是回文串的索引下标如果是回文串的话其实索引startIndex不变只需要将终止索引1, 即i1。例如aab startIndex1, i2那么待判断的回文串就是ab.假设ab是回文串那么索引 startIndex, i1 就代表着aab的ab。So, do you understand? if self.isPalinDrome(s, startIndex, i):self.path.append(s[startIndex:i1])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:i1])else:continueself.traceBacking(s, i1)self.path.pop()def isPalinDrome(self,s,startIndex, end):i startIndexj endwhile ij:if s[i] ! s[j]:return Falsei 1j -1return Truedef partition(self, s):self.result []self.traceBacking(s, 0)return self.result
