难度: Medium
给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "google" 输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]
示例 2：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 3：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s 仅由小写英文字母组成注意：本题与主站 131 题相同： https://leetcode-cn.com/problems/palindrome-partitioning/
运行时间: 66 ms
内存: 30.3 MB
class Solution:
def partition(self, s: str) -> List[List[str]]:
ans = [[[]]]
for i in range(len(s)):
tmp = []
for j in range(i + 1):
cur = s[j:i+1]
if cur == cur[::-1]:
tmp.extend(ls + [cur] for ls in ans[j])
ans.append(tmp)
return ans[-1]
题解采用了动态规划的方法来解决问题。首先，定义一个列表 `ans` 来存储从字符串起始到每个位置的所有可能的回文分割列表。`ans[i]` 存储的是对字符串 `s[0:i]` 的所有回文分割方式。对于每个字符 `s[i]`，通过内部循环检查以 `j` 开始到 `i` 结束的子串 `s[j:i+1]` 是否为回文串。如果是回文，那么将 `ans[j]` 中的每个分割方案加上这个回文串，形成新的分割方案，并加到临时列表 `tmp` 中。最后将 `tmp` 加入到 `ans` 中。整个过程结束后，`ans[-1]` 将包含对整个字符串 `s` 的所有回文分割方案。
时间复杂度: O(n^3)
空间复杂度: O(n*2^n)
class Solution:
def partition(self, s: str) -> List[List[str]]:
ans = [[[]]] # 初始化，0位置先放一个空列表
for i in range(len(s)):
tmp = [] # 临时存储所有到当前位置的分割方案
for j in range(i + 1):
cur = s[j:i+1] # 当前考虑的子串
if cur == cur[::-1]: # 检查子串是否为回文
# 若是回文，则将之前的所有分割方案加上这个回文串
tmp.extend(ls + [cur] for ls in ans[j])
ans.append(tmp) # 更新动态规划的结果列表
return ans[-1] # 返回整个字符串的所有分割方案
动态规划方法适用于这类问题因为它可以将问题分解成重叠的子问题，并通过解决这些子问题来解决整个问题。在分割回文串的问题中，我们可以通过考虑较小的子串的解来构建整个字符串的解，这样可以避免重复计算，并且能有效地利用之前计算的结果。相对于回溯算法，动态规划在处理大型数据时通常更高效，尤其是当回文分割的可能性非常多时，动态规划可以避免大量的重复计算。
`ans[j]`中的每个分割方案都是由之前步骤的有效回文分割构成。这是因为在动态规划中，我们从基础开始构建解决方案，每次迭代中只有当识别到一个子串是回文时，才会考虑将这个子串加入到分割方案中。因此，每一步都基于已经验证的回文分割来进行扩展，确保了`ans[j]`中存储的每个方案都是有效的。
检查子串`s[j:i+1]`是否为回文，通过比较该子串与其逆序字符串是否相等（`cur == cur[::-1]`）是一种直接且清晰的方法。这种方法简单易懂，但效率上可能不是最优的，因为每次检查都需要O(n)的时间来生成逆序字符串并比较，其中n是子串的长度。尽管如此，对于较短的字符串或者在数据规模较小的情况下，这种方法通常表现得足够好。优化的方法可以包括使用额外的动态规划数组来存储回文检查的结果，从而减少重复计算。