回文串

分割回文串

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

class Solution:
    def dfs(self, s, idx, path):
        """ idx:当前处理到的第idx个字符 """
        if idx == len(s):
            self.res.append(path)
            return
        
        for i in range(idx, len(s)):
            if self.isPail[idx][i]:
                self.dfs(s, i+1, path +[s[idx:i+1]])


    def partition(self, s: str) -> List[List[str]]:
        if len(s) < 2: return [[s]]
        n = len(s)
        self.isPail = [[False]*n for _ in range(n)]
        self.isPail[0][0] = True
        for j in range(1, n):
            for i in range(j+1):
                if s[i] == s[j] and (j-1 - (i+1) + 1 < 2 or self.isPail[i+1][j-1] == True):
                    self.isPail[i][j] = True
        self.res = []
        path = []
        self.dfs(s, 0, path)
        return self.res