1 题目
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：
输入：s = “a”
输出：[[“a”]]
2 解析
当我们在判断 s[i…j] 是否为回文串时，常规的方法是使用双指针分别指向 ii和 j，每次判断两个指针指向的字符是否相同，直到两个指针相遇。然而这种方法会产生重复计算，例如下面这个例子：
当 s=aaba 时，对于前 2个字符aa，我们有 22种分割方法 [aa] 和 [a,a]，当我们每一次搜索到字符串的第i=2 个字符b 时，都需要对于每个 s[i…j] 使用双指针判断其是否为回文串，这就产生了重复计算。
因此，我们可以将字符串 s 的每个子串]s[i…j] 是否为回文串预处理出来，使用动态规划即可。设f(i,j) 表示s[i…j] 是否为回文串，那么有状态转移方程：
\begin{cases} \texttt{True}, & \quad i \geq j \\ f(i+1,j-1) \wedge (s[i]=s[j]), & \quad \text{otherwise} \end{cases}
其中∧ 表示逻辑与运算，即 s[i…j] 为回文串，当且仅当其为空串（i>j），其长度为 1（i=j），或者首尾字符相同且s[i+1…j−1] 为回文串。
预处理完成之后，我们只需要 O(1) 的时间就可以判断任意 s[i…j] 是否为回文串了。
3 Python实现
class Solution:
def partition(self, s: str) -> List[List[str]]:
n = len(s)
f = [[True]*n for _ in range(n)]
for i in range(n-1,-1,-1):
for j in range(i+1,n):
f[i][j] = (s[i]==s[j]) and f[i+1][j-1]
res = []
tmp = []
def dfs(i):
if i==n:
res.append(tmp[::])
return
for j in range(i,n):
if f[i][j]:
tmp.append(s[i:j+1])
dfs(j+1)
tmp.pop()
dfs(0)
return res
