代码随想录算法训练营第二十六天（回溯算法篇）|131. 分割回文串

131. 分割回文串

题目链接：131. 分割回文串 - 力扣（LeetCode）

思路

分割字串和组合的题目有异曲同工之妙。

组合：选好数组中第一个数，接着选数组中第一个后面的数，进入递归。第一个树层代表选的第一个数的可能性。startIdx为选的数在数组中的序数。

分割：选好子串中第一个分割的部分，接着选子串中后面分割的部分。第一个树层代表分割的第一个子串的可能性。startIdx为每一个字串的“分割线”。

代码实现

class Solution(object):
    def isPalin(self, s, start, end):
        i, j = start, end
        while i<j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True
        
    def 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: i+1])         
                self.backtracking(s, i+1, path, result)
                # 每一个递归之后，startIdx都会加一（体现在i+1），直到等于字串的长度，代表当前已 经分割完s了。
                path.pop()

        return result

    def partition(self, s):
        result = []
        self.backtracking(s, 0, [],result)
        return result