共计 3548 个字符，预计需要花费 9 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 「131. 宰割回文串」，难度为 「中等」。
给你一个字符串 s，请你将 s 宰割成一些子串，使每个子串都是「回文串」。
返回 s 所有可能的宰割计划。
回文串 是正着读和反着读都一样的字符串。
示例 1：
| 输出：s = "aab" | |
| 输入：[["a","a","b"],["aa","b"]] |
示例 2：
| 输出：s = "a" | |
| 输入：[["a"]] |
提醒：
- 1 <= s.length <= 16
- s 仅由小写英文字母组成
动静布局 + 回溯算法
求所有的宰割计划，但凡求所有计划的题基本上都没有什么优化计划，就是「爆搜」。
问题在于，爆搜什么？
显然咱们能够爆搜每个回文串的终点。如果有间断的一段是回文串，咱们再对剩下间断的一段持续爆搜。
为什么可能间接接着剩下一段持续爆搜？
因为任意的子串最终必然可能宰割成若干的回文串（最坏的状况下，每个回文串都是一个字母）。
所以咱们每次往下爆搜时，只须要保障本身间断一段是回文串即可。
举个🌰 来感触下咱们的爆搜过程，假如有样例 abababa，刚开始咱们从终点第一个 a 进行爆搜：
- 发现
a是回文串，先将a宰割进去，再对剩下的bababa进行爆搜 - 发现
aba是回文串，先将aba宰割进去，再对剩下的baba进行爆搜 - 发现
ababa是回文串，先将ababa宰割进去，再对剩下的ba进行爆搜 -
发现
abababa是回文串，先将abababa宰割进去，再对剩下的 \`\` 进行爆搜…
而后再对下一个终点（下个字符）b 进行爆搜？
不须要。
因为单个字符自身形成了回文串，所以以 b 为终点，b 之前形成回文串的计划，必然笼罩在咱们以第一个字符为终点所开展的爆搜计划内（在这里就是对应了上述的第一步所开展的爆搜计划中）。
因而咱们只须要以首个字符为终点，枚举以其结尾所有的回文串计划，退出汇合，而后对剩下的字符串局部持续爆搜。就能做到以任意字符作为回文串终点进行宰割的成果了。
肯定要好好了解下面那句话 ~
剩下的问题是，咱们如何疾速判断间断一段 是否为回文串，因为爆搜的过程每个地位都能够作为宰割点，复杂度为 的。
因而咱们不可能每次都应用双指针去线性扫描一遍 判断是否回文。
一个直观的做法是，咱们先预处理除所有的，代表 这一段是否为回文串。
预处理 的过程能够用递推去做。
要想，必须满足以下两个条件：
因为状态 依赖于状态，因而须要咱们左端点 是 「从大到小」 进行遍历；而右端点 是 「从小到大」 进行遍历。
因而，咱们的遍历过程能够整顿为：右端点 始终往右挪动（从小到大），在 固定状况下，左端点 在 在右边开始，始终往左挪动（从大到小）。
代码：
| class Solution {public List<List<String>> partition(String s) {int n = s.length(); | |
| char[] cs = s.toCharArray(); | |
| // f[i][j] 代表 [i, j] 这一段是否为回文串 | |
| boolean[][] f = new boolean[n][n]; | |
| for (int j = 0; j < n; j++) {for (int i = j; i >= 0; i--) {// 当 [i, j] 只有一个字符时，必然是回文串 | |
| if (i == j) {f[i][j] = true; | |
| } else {// 当 [i, j] 长度为 2 时，满足 cs[i] == cs[j] 即回文串 | |
| if (j - i + 1 == 2) {f[i][j] = cs[i] == cs[j]; | |
| // 当 [i, j] 长度大于 2 时，满足 (cs[i] == cs[j] && f[i + 1][j - 1]) 即回文串 | |
| } else {f[i][j] = cs[i] == cs[j] && f[i + 1][j - 1]; | |
| } | |
| } | |
| } | |
| } | |
| List<List<String>> ans = new ArrayList<>(); | |
| List<String> cur = new ArrayList<>(); | |
| dfs(s, 0, ans, cur, f); | |
| return ans; | |
| } | |
| /** | |
| * s: 要搜寻的字符串 | |
| * u: 以 s 中的那一位作为回文串宰割终点 | |
| * ans: 最终后果集 | |
| * cur: 以后后果集 | |
| * f: 疾速判断 [i,j] 是否为回文串 | |
| */ | |
| void dfs(String s, int u, List<List<String>> ans, List<String> cur, boolean[][] f) {int n = s.length(); | |
| if (u == n) ans.add(new ArrayList<>(cur)); | |
| for (int i = u; i < n; i++) {if (f[u][i]) {cur.add(s.substring(u, i + 1)); | |
| dfs(s, i + 1, ans, cur, f); | |
| cur.remove(cur.size() - 1); | |
| } | |
| } | |
| } | |
| } |
- 工夫复杂度：动静布局预处理的复杂度为；爆搜过程中每个字符都能够作为宰割点，并且有宰割与不宰割两种抉择，计划数量为，每个字符都须要往后查看残余字符的宰割状况，复杂度为。整体复杂度为
- 空间复杂度：动静布局局部的复杂度为；计划数量最多为，每个计划都是残缺字符串
s的宰割，复杂度为，整体复杂度为
总结
对于此类要枚举所有计划的题目，咱们都应该先想到「回溯算法」。
「回溯算法」从算法定义上来说，不肯定要用 DFS 实现，但通常联合 DFS 来做，难度是最低的。
「回溯算法」依据以后决策有多少种抉择，对应了两套模板。
每一次独立的决策只对应 抉择 和 不选 两种状况：
- 确定完结回溯过程的 base case
- 遍历每个地位，对每个地位进行决策（做抉择 -> 递归 -> 撤销抉择）
| void dfs(以后地位, 门路(以后后果), 后果集) {if (以后地位 == 完结地位) {后果集.add(门路); | |
| return; | |
| } | |
| 抉择以后地位; | |
| dfs(下一地位, 门路(以后后果), 后果集); | |
| 撤销抉择以后地位; | |
| dfs(下一地位, 门路(以后后果), 后果集); | |
| } |
每一次独立的决策都对应了多种抉择（通常对应了每次决策能抉择什么，或者每次决策能抉择多少个 …）:
- 确定完结回溯过程的 base case
- 遍历所有的「抉择」
- 对抉择进行决策 (做抉择 -> 递归 -> 撤销抉择)
| void dfs(抉择列表, 门路(以后后果), 后果集) {if (满足完结条件) {后果集.add(门路); | |
| return; | |
| } | |
| for (抉择 in 抉择列表) { | |
| 做抉择; | |
| dfs(门路’, 抉择列表, 后果集); | |
| 撤销抉择; | |
| } | |
| } |
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.131 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先将所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
