本文共 1220 字，大约阅读时间需要 4 分钟。

题目：（中等）

标签：回溯算法、字符串

解法一：

class Solution:    def __init__(self):        self.ans = []        self.now = []        self.s = ""        self.is_palindrome = []        self.size = 0    def partition(self, s: str) -> List[List[str]]:        self.size = len(s)        self.s = s        # 计算是否为回文串        self.is_palindrome = [[False] * self.size for _ in range(self.size)]        for r in range(self.size):            for l in range(r, -1, -1):                if s[l] == s[r] and (r - l <= 2 or self.is_palindrome[l + 1][r - 1]):                    self.is_palindrome[l][r] = True        self.dfs(0, 0)        return self.ans    def dfs(self, i1, i2):        if i2 == self.size - 1:            if self.is_palindrome[i1][i2]:                self.now.append(self.s[i1:i2 + 1])                self.ans.append(list(self.now))                self.now.pop()        else:            # 在当前位置切分            if self.is_palindrome[i1][i2]:                self.now.append(self.s[i1:i2 + 1])                self.dfs(i2 + 1, i2 + 1)                self.now.pop()            # 不在当前位置切分            self.dfs(i1, i2 + 1)

转载地址：https://dataartist.blog.csdn.net/article/details/112603764 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！