131. 分割回文串

https://leetcode-cn.com/problems/palindrome-partitioning/

解法一：回溯

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        self.res = []
        tmp = []  #辅助
        self.dfs(s, tmp, 0)
        return self.res
    
    #dfs回溯，从idx后开始处理
    def dfs(self, s, tmp, idx):
        if idx == len(s):  #若能走到最后，写入res
            self.res.append(list(tmp))
        #截取长度从1开始，分别试探
        for i in range(idx+1, len(s)+1):            
            if self.isPalindrome(s[idx:i]):
                tmp.append(s[idx:i])
                self.dfs(s, tmp, i)
                tmp.pop()
        
    #判断是否回文    
    def isPalindrome(self, s):
        return s == s[::-1]