Palindrome Partitioning
回文从左向右和从右向左读都相同。将字符串 s 切分成一个或多个片段，使每个片段都是回文，并返回所有切分方式。
按顺序用各片段表示每种切分方式，并用 | 连接：将 aab 切分为 a、a 和 b，得到 a|a|b。按字符编码升序排列这些切分方式，因此 | 排在所有小写字母之后。
函数
- sstring
- 要截取的小写字母字符串
- 返回值string-array
- 将 s 拆分成回文串的所有方式，用 | 分隔各部分，并按升序排列
约束条件
1 ≤ s.length ≤ 11s只包含小写英文字母。- 由 11 个相同字母组成的字符串有 1,024 种拆分方式，这是最多的答案。
示例
- 输入
- s = "aab"
- 输出
- ["aa|b", "a|a|b"]
- 解释
- 只有
aa|b和a|a|b的所有部分都是回文；a|ab在ab上不符合条件。aa|b排在前面：在第二个字符处，它是a，而另一个是|，后者的排序位置在所有字母之后。
- 输入
- s = "abba"
- 输出
- ["abba", "a|bb|a", "a|b|b|a"]
- 解释
abba本身就是一个回文串，所以未切分的字符串也是一种切分，并且排序最靠前：它的第二个字符是字母。a|bb|a排在a|b|b|a前面：在第四个字符处，前者是b，而后者是|。
进阶
对于长度不超过 2,000 的字符串，你能找出将 s 切分成回文串所需的最少切割次数吗？
提示
逐个打开提示，每个都会多透露一点。
单个字母始终是回文，因此每个字符串至少有一种拆分方式。看看相邻字母之间的间隙：拆分就是对每个间隙选择是否在此处切开。
从左到右进行拆分。第一部分必须是回文前缀；选定它之后，剩下的字符串仍然是同一个问题。用一个表记录
s[i..j]是否为回文，这样每次检查都只需 O(1)。从下一段开始的位置进行递归，并尝试每个能让当前片段成为回文的结束索引。由于
|的排序位置在所有字母之后，先尝试最长的片段，就能让拆分结果按顺序排列。
题解
字母之间的 n-1 个间隙都可以选择切开或不切开，因此共有 2^(n-1) 种切分，而且它们都可能是答案。你无法减少输出量，但可以跳过不符合条件的切分：从左到右构建每种切分，只切出回文片段，并从预先填好的表中读取回文。
尝试每一种切割组合
思路
用从 0 到 2^(n-1)-1 的整数为切分编号，每一位表示是否切开一个间隙。如果每一段都是回文，就保留对应编号的切分。
如果第一个间隙对应最高位，按数字递增顺序排列，就能按升序列出这些切分。对于两个数字，它们最高位的不同之处对应最早的一个间隙，在这个间隙，一个数字切开了，而另一个没有。在它之前，字符串都相同；在这个间隙，较小的数字对应一个字母，较大的数字对应 |，而 | 的排序位置在所有字母之后。对于 aab，1 对应 aa|b，3 对应 a|a|b。
对于 11 个字母，需要处理 1,024 个掩码，每个掩码对应 11 个字母。浪费出在被拒绝的切分上：abcdefghijk 会构造全部 1,024 种切分，才能找到一个答案。
算法
- 将
mask从 0 循环到2^(n-1)-1。 - 遍历字母；在字母
i后结束一个片段，当i是最后一个索引，或mask的第n-2-i位已设置时。 - 用两个指针从两端向中间移动，检查每个片段。
- 如果每个片段都是回文，就用
|连接这些片段，并将字符串添加到答案中。 - 返回答案；答案已经排好序，因为第一个间隔对应最高位。
def partition(s):
n = len(s)
result = []
# Bit (n-2-i) of mask says whether to cut after s[i]. Counting the
# masks up from 0 lists the splits in sorted order.
for mask in range(1 << (n - 1)):
pieces = []
start = 0
for i in range(n):
if i == n - 1 or (mask >> (n - 2 - i)) & 1:
pieces.append(s[start:i + 1])
start = i + 1
if all(piece == piece[::-1] for piece in pieces):
result.append("|".join(pieces))
return result使用回文表进行回溯
思路
第一段是一个回文前缀 s[0..end]，剩下部分的拆分问题与从 end+1 开始的问题相同。因此，backtrack(start) 会尝试每个使 s[start..end] 成为回文的 end，添加这一段，递归调用，然后将它移除。每个分支最终都会得到一个答案，因为单个字母也是回文，所以工作量与输出大小相符：对于 abcdefghijk，搜索只会沿着一条路径进行。
许多分支都会判断 s[start..end] 是否为回文，因此可以从表中读取结果：当 s[i] == s[j] 且内部的 s[i+1..j-1] 为 1，或者这一段最多有 2 个字母时，s[i..j] 的值为 1。
按索引从后往前尝试 end，就能得到排序后的输出。首段不同的两种拆分会一直相同，直到较短首段的末尾；在这里，较短首段有 |，较长首段则有一个字母，因此较长的首段排序靠前。
算法
- 从
n-1到 0 填写pal[i][j]：满足s[i] == s[j]，并且j-i < 2或pal[i+1][j-1]。 - 编写
backtrack(start)。如果start等于n，就用|连接当前片段，并保存这个字符串。 - 否则，让
end从n-1循环到start，如果pal[start][end]不成立，就跳过。 - 将
s[start..end]添加到片段中，调用backtrack(end+1)，然后移除该片段。 - 调用
backtrack(0)，并返回已排序的拆分结果。
def partition(s):
n = len(s)
# pal[i][j] is True when s[i..j] reads the same both ways.
pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
result = []
parts = []
def backtrack(start):
if start == n:
result.append("|".join(parts))
return
# Longest piece first: "|" sorts after every letter, so a longer
# first piece gives a smaller string and the output stays sorted.
for end in range(n - 1, start - 1, -1):
if pal[start][end]:
parts.append(s[start:end + 1])
backtrack(end + 1)
parts.pop()
backtrack(0)
return result
易错点和边界情况
- 先尝试最短的一段。切分结果正确，但顺序错误：
a|a|b排在aa|b前面。 - 最后使用遵循语言或区域规则的比较方式排序，这可能会让
|排在字母前面。比较字符编码，或按顺序生成切分结果。 - 填写回文表时让
i递增。这样会在计算pal[i+1][j-1]之前读取它；应从n-1开始递减填写i。 - 把包含末尾位置的
end和不包含末尾位置的子字符串终点混为一谈。片段s[start..end]有end-start+1个字母。 - 保存共享的片段列表，而不是拼接后的字符串。搜索过程会不断修改这个列表，因此保存的每一项最后都会变成相同的内容。
常见问题3
回文分割的时间复杂度是多少？
对于由相同字母组成的字符串，所有 2^(n-1) 种拆分都是答案，每种答案最多包含 2n-1 个字符：O(n × 2^n)。没有方法能比这更快，因为写出答案本身也需要同样多的时间。回文表会增加 O(n²) 的时间和空间开销，递归则需要 O(n)。
一个字符串可以有多少种回文划分？
最多有 2^(n-1) 种，每种对应一种从 n-1 个间隙中选择切分位置的方式。由相同字母组成的字符串可以达到这个上限：11 个字母有 1,024 种切分方式。没有重复字母的字符串恰好只有一种切分方式，每个字母单独成段。
回文分割使用的是动态规划还是回溯？
两种方法都会用到。列出最多 2^(n-1) 种拆分，需要通过逐步构建每种拆分来进行搜索：回溯。动态规划会生成一个记录子字符串是否为回文的表，供搜索读取，并在 O(n²) 时间内填好。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def partition(s):
# 在这里编写代码测试 #1
测试 #2
参数
s = "aab"
预期输出
["aa|b", "a|a|b"]