网站建设课程设计文献综述,刷关键词排名软件,太原高端网站建设,百度公司官网131. 分割回文串
题目链接#xff1a;131. 分割回文串 - 力扣#xff08;LeetCode#xff09;
思路
分割字串和组合的题目有异曲同工之妙。
组合#xff1a;选好数组中第一个数#xff0c;接着选数组中第一个后面的数#xff0c;进入递归。第一个树层代表选的第一个数…131. 分割回文串
题目链接131. 分割回文串 - 力扣LeetCode
思路
分割字串和组合的题目有异曲同工之妙。
组合选好数组中第一个数接着选数组中第一个后面的数进入递归。第一个树层代表选的第一个数的可能性。startIdx为选的数在数组中的序数。
分割选好子串中第一个分割的部分接着选子串中后面分割的部分。第一个树层代表分割的第一个子串的可能性。startIdx为每一个字串的“分割线”。
代码实现
class Solution(object):def isPalin(self, s, start, end):i, j start, endwhile ij:if s[i] ! s[j]:return Falsei 1j - 1return Truedef backtracking(self, s, startIdx, path, result):if startIdx len(s): result.append(path[:])return for i in range(startIdx, len(s)):if self.isPalin(s, startIdx, i):path.append(s[startIdx: i1]) self.backtracking(s, i1, path, result)# 每一个递归之后startIdx都会加一体现在i1直到等于字串的长度代表当前已 经分割完s了。path.pop()return resultdef partition(self, s):result []self.backtracking(s, 0, [],result)return result
