题目描述
这是 LeetCode 上的 131. 分割回文串 ,难度为 中等。
Tag : 「回文串」、「回溯算法」、「动态规划」
给你一个字符串 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
之前构成回文串的方案,必然覆盖在我们以第一个字符为起点所展开的爆搜方案内(在这里就是对应了上述的第一步所展开的爆搜方案中)。
因此我们只需要以首个字符为起点,枚举以其开头所有的回文串方案,加入集合,然后对剩下的字符串部分继续爆搜。就能做到以任意字符作为回文串起点进行分割的效果了。
一定要好好理解上面那句话 ~
剩下的问题是,我们如何快速判断连续一段 [i, j]
是否为回文串,因为爆搜的过程每个位置都可以作为分割点,复杂度为 O(2n)O(2^n)O(2n) 的。
因此我们不可能每次都使用双指针去线性扫描一遍 [i, j]
判断是否回文。
一个直观的做法是,我们先预处理除所有的 f[i][j]
,f[i][j]
代表 [i, j]
这一段是否为回文串。
预处理 f[i][j]
的过程可以用递推去做。
要想 f[i][j] == true
,必须满足以下两个条件:
f[i + 1][j - 1] == true
s[i] == s[j]
由于状态 f[i][j]
依赖于状态 f[i + 1][j - 1]
,因此需要我们左端点 i
是从大到小进行遍历;而右端点 j
是从小到大进行遍历。
因此,我们的遍历过程可以整理为:右端点 j
一直往右移动(从小到大),在 j
固定情况下,左端点 i
在 j
在左边开始,一直往左移动(从大到小)
代码:
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); } } } } 复制代码
- 时间复杂度:动态规划预处理的复杂度为 O(n2)O(n^2)O(n2);爆搜过程中每个字符都可以作为分割点,并且有分割与不分割两种选择,方案数量为 2n−12^{n - 1}2n−1,每个字符都需要往后检查剩余字符的分割情况,复杂度为 O(n)O(n)O(n)。整体复杂度为 O(n∗2n)O(n * 2^n)O(n∗2n)
- 空间复杂度:动态规划部分的复杂度为 O(n2)O(n^2)O(n2);方案数量最多为 2n−12^{n - 1}2n−1,每个方案都是完整字符串
s
的分割,复杂度为 O(n)O(n)O(n),整体复杂度为 O(n∗2n)O(n * 2^n)O(n∗2n)
总结
对于此类要枚举所有方案的题目,我们都应该先想到「回溯算法」。
「回溯算法」从算法定义上来说,不一定要用 DFS 实现,但通常结合 DFS 来做,难度是最低的。
「回溯算法」根据当前决策有多少种选择,对应了两套模板。
每一次独立的决策只对应 选择 和 不选 两种情况:
- 确定结束回溯过程的 base case
- 遍历每个位置,对每个位置进行决策(做选择 -> 递归 -> 撤销选择)
void dfs(当前位置, 路径(当前结果), 结果集) { if (当前位置 == 结束位置) { 结果集.add(路径); return; } 选择当前位置; dfs(下一位置, 路径(当前结果), 结果集); 撤销选择当前位置; dfs(下一位置, 路径(当前结果), 结果集); } 复制代码
每一次独立的决策都对应了多种选择(通常对应了每次决策能选择什么,或者每次决策能选择多少个 ...):
- 确定结束回溯过程的 base case
- 遍历所有的「选择」
- 对选择进行决策 (做选择 -> 递归 -> 撤销选择)
void dfs(选择列表, 路径(当前结果), 结果集) { if (满足结束条件) { 结果集.add(路径); return; } for (选择 in 选择列表) { 做选择; dfs(路径’, 选择列表, 结果集); 撤销选择; } } 复制代码
拓展
刚好最近在更新「回溯算法」的相关题解,以下题目可以加深你对「回溯」算法的理解和模板的运用:
17. 电话号码的字母组合(中等) : 从一道「回溯算法」经典题与你分享回溯算法的基本套路
39. 组合总和(中等) : DFS + 回溯算法,以及如何确定一道题是否应该使用 DFS + 回溯来求解
40. 组合总和 II(中等) : 【回溯算法】求目标和的组合方案(升级篇)
216. 组合总和 III(中等) : 【回溯算法】借助最后一道「组合总和」问题来总结一下回溯算法
最后
这是我们「刷穿 LeetCode」系列文章的第 No.131
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。