力扣刷题Day 66：分割回文串（131）

1.题目描述

2.思路

用了回溯的方法。首先写一个验证字符串是否是回文串的函数，然后遍历s，依次判断从当前字符到下一字符是否是回文串，是的话继续往后走，不是的话往回退。

3.代码（Python3）

class Solution:def partition(self, s: str) -> List[List[str]]:def palindrome(sub_s):left, right = 0, len(sub_s) - 1while left < right:if sub_s[left] != sub_s[right]:return Falseleft += 1right -= 1return Truedef backtrack(start, tmp):if start == len(s):res.append(list(tmp))returnfor i in range(start, len(s)):if palindrome(s[start : i + 1]):tmp.append(s[start : i + 1])backtrack(i + 1, tmp)tmp.pop()res = []backtrack(0, [])return res

4.执行情况

5.感想

这次回溯写得很快。