分割回文串

Leetcode Link: 131. 分割回文串 - 力扣（LeetCode）

题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

解法一

思路：自己的思路，用回溯的算法，虽然是跟着代码随想录做的，但是没看他的题解

如何判断回文子串可以参考 最长回文子串题中的check函数

正式开始

在给定的 s 中切割出所有回文子串的切割方案，思路是： 指针从 choose 初始 0 位置开始，先找第一个回文子串，找到之后，新的 choose 就是该子串的后面一个位置开始到旧的 choose 结束，也就是 new_choose = choose[r+1:]，r 是上一个回文子串的右边界（两者注意别重合）。

因此，判断回文子串的那个函数，不仅需要给出回文子串的内容（没有就是""），也要给出当前的这个回文子串在当前的choose中的右边界索引

然而，切割问题是需要包含输入的所有内容，不能遗漏的 在本题中，意味着在每一层中每次找到的回文子串的左边界，都需要和上一层回文子串（也就是上一个）的右边界是挨着的。如果直接使用 for idx, c in enumerate(choose) 直接找回文子串，可能导致的结果是该层新找到的回文子串左边界和上一层的回文子串右边界不挨着。

在本题中，由于我们每次递归时候都会送进去当前层的 choose，所以我们在找当前层的回文子串的时候，需要判定该层找到的回文子串的左边界起点一定是 0，否则就会导致当前层的回文子串左边界和上一层的回文子串右边界中间有遗漏的元素。 因此，在判断回文子串的时候，我们同样需要返回回文子串的左边界起点，并在外面判断它是不是0

何时继续往下遍历 当找到回文子串的时候，就往下遍历，找不到就一直在这层找，直到结束。

找到满足题解的答案 因为题目是切割方案，也就是需要看完输入中所有的字符。 我们上面提到了，找到回文子串的时候才继续往下走，因此只要能走到结束（当前递归函数的 choose 为空，即看完所有的字符）就说明当前的 path 里是一个正确的切割方案。

题解：

class Solution:
 
	def check(self, chose, left, right):
        # 含左含右
        tarS = []
        # 控制边界
        while(left >= 0 and right <= len(chose)-1):
            if chose[left] == chose[right]:
                tarS = chose[left:right+1]
                left -= 1
                right += 1
            else:
                break
        # 当前的回文子串左边界起点（含）
        left_start = left + 1 # 包含这个的
        # 实际上这个tarS是不包含这个 right 的，这个right可以说是下一个串的left_bound（含）,因为+=1了在出来前
        return tarS, right, left_start 
 
    def partition(self, s: str) -> List[List[str]]:
        def backtracking(choose):
            nonlocal res, path
 
			# 停止条件，同时也说明是一个正确的分割
            if choose == '':
                res.append(copy.deepcopy(path))
                return
 
            for idx, c in enumerate(choose):
                
                s1, right1, ls1 = self.check(choose, idx, idx)
                if s1 != [] and ls1 == 0: # 是个紧挨着上一个的回文串，添加到路径并进行下一层遍历
                    path.append(s1)
                    backtracking(choose[right1:])
                    path.pop()
 
                s2, right2, ls2 = self.check(choose, idx,idx+1)
                if s2 != [] and ls2 == 0: # 是个回文串，添加到路径并进行下一层遍历
                    path.append(s2)
                    backtracking(choose[right2:])
                    path.pop()
        
        res = []
        path = []
        backtracking(s)
        return res

解法二

思路：代码随想录的解法

实际上，没必要用那么复杂的方法来判断回文，只要逆序相等就行

切割问题，可以抽象的考虑切割线，解法一中利用了left_bound来判断切割的时候是挨着的，这块模拟了切割，而本题中直接考虑切割线，就是一个索引来模拟切割

题解：

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def backtracking(start_index):
            nonlocal s, path, res
            if start_index >= len(s):
                res.append(path[:]) # 使用这个也行，会拉成一维的
                return
            # 在 i 和 i+1 之间切割
            # i 为上一个最后，i+1为新的起点
            for i in range(start_index, len(s)):
                tmp = s[start_index:i+1]
                if tmp == tmp[::-1]:
                    path.append(tmp)
                    backtracking(i+1) # 想想这里为什么是 i 
                    path.pop()
        
        res = []
        path = []
        backtracking(0)
        return res   

请务必重写此代码，此代码的几个索引值我怎么想都想不对!

启发和联系

索引！索引！索引！