力扣每日一题——分割回文串
目录
题目链接：131. 分割回文串 - 力扣（LeetCode）
题目描述
思路
具体步骤：
解法一：双指针判断+回溯
Java写法：
C++写法：
运行时间
时间复杂度和空间复杂度
解法二：采用动态规划预处理+回溯
Java写法：
C++写法：
运行时间
时间复杂度和空间复杂度
总结
题目链接：131. 分割回文串 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
思路
题目是给定一个字符串s，要把s分割成若干子串，每个子串都是回文。然后返回所有可能的分割方案。比如例子中的aab，输出是两种分法。那这题怎么想呀？
首先，我们得理解回文是什么，就是正读反读都一样的字符串。比如单个字符肯定是回文，两个相同字符也是，像"aa"。那问题的关键在于如何找到所有可能的分割方式，使得每个分割后的子串都是回文。
第一时间你能想到思路应该是回溯法。因为我们需要枚举所有可能的分割方式，然后检查每个子串是否符合条件。回溯法比较适用于这种组合的问题，可以逐步构建解，并在不满足条件时回溯。
那具体的步骤大概是什么样的？比如，从字符串的起始位置开始，尝试分割出不同长度的子串，判断是否为回文。如果是的话，就将这个子串加入当前路径，然后递归处理剩下的部分。当处理到字符串末尾时，就将当前路径加入结果列表中。
举个例子，比如对于"aab"，第一个分割位置可以是0到0（即第一个字符a），然后剩下的部分是"ab"。接着在剩下的部分继续分割，比如分割出a，剩下b。最后分割b，得到一个完整的路径["a","a","b"]。或者，第一次分割0到1（即aa），剩下的b，分割之后得到["aa","b"]。
那么问题就来了，怎么实现这个过程呢？我们需要一个辅助函数，用来判断某个子串是否是回文。比如，给定起始和结束索引，判断s的子串是否是回文，那这个其实就是涉及到判断回文串的操作了。
然后，主函数使用回溯的方法，维护当前路径和起始位置。每次从起始位置开始，尝试所有可能的结束位置（即从start到字符串末尾），如果s[start..end]是回文，就将该子串添加到路径中，然后递归处理end+1的位置。如果处理到字符串末尾（start >= s.length()），则将当前路径添加到结果列表中。
这样，回溯的过程会遍历所有可能的分割方式，而只有符合条件的回文分割才会被保留下来。
具体到Java的实现方式，可以使用一个List<List<String>>来保存结果，然后一个List<String> current来记录当前的分割路径。每次递归调用时，循环尝试不同的结束位置，如果发现回文子串，就进行递归。
判断回文的方法，可以用双指针法，从两端向中间比较。或者，可以用动态规划预处理回文信息，以提高效率。比如，先生成一个二维数组dp，其中dp[i][j]表示s从i到j的子串是否是回文。这样在多次判断时可以节省时间。
对于字符串长度较大的情况，预处理应该会更高效。
具体步骤：
1. 主函数中，初始化结果列表和当前路径，调用回溯函数。
2. 回溯函数的参数包括字符串s，起始位置start，当前路径，结果列表。
3. 在回溯函数中，如果start等于s的长度，说明已经处理完整个字符串，将当前路径添加到结果。
4. 否则，从start开始，遍历到字符串末尾的每个可能的结束位置end。
5. 对于每个end，判断s[start..end]是否是回文。
6. 如果是，就将该子串加入当前路径，然后递归处理end+1的位置。
7. 递归返回后，需要回溯，将刚才加入的子串移除，以尝试下一个可能的结束位置。
这样，整个过程就能穷举所有可能的分割方式，而只有符合回文条件的才会被保留。
这样操作的话时间复杂度，这会比较高的。比如，每个位置都有分割和不分割的可能，所以时间复杂度可能接近O()，但因为有回文的条件剪枝，实际会好一些。不过对于较短的字符串来说，还是可以接受的。
举个例子，比如s="aaa"，那么可能的每个分割点都可以是回文。所以分割方式很多。这时候回溯法需要处理很多情况，但因为每个判断都是O(n)的时间，所以不知道能不能过啊。
对于判断回文的函数，比如isPalindrome(s, start, end)。实现的话，可以写一个循环，从start到end，比较s.charAt(start)和s.charAt(end)，然后start++，end--，直到相遇。如果有不相等的，返回false，否则返回true。
这样就构成了解法一。
解法一：双指针判断+回溯
Java写法：
class Solution {
public List<List<String>> partition(String s) {
// 用于存储结果
List<List<String>> result = new ArrayList<>();
// 进入回溯
// s是要判断切割的字符串，0是起始位置，new ArrayList是当前的路径，result是结果便于随时加减
backtrack(s, 0, new ArrayList<>(), result);
return result;
}
/**
回溯寻找操作
*/
private void backtrack(String s, int start, List<String> current, List<List<String>> result) {
// 先判断是否已经是末尾了，如果是直接就将结果加进去
if (start == s.length()) {
// 记得要格式化为ArrayList再放入
result.add(new ArrayList<>(current));
return;
}
// 寻找逻辑，不断的修改分割点
for (int end = start; end < s.length(); end++) {
// 判断区间字符串是否为回文串
if (isPalindrome(s, start, end)) {
// 是，那就加入当前的结果
current.add(s.substring(start, end + 1));
// 然后继续递归，找其他分割点的
backtrack(s, end + 1, current, result);
// 递归结束出来，就是已经加入了或者后面不是回文串的，将当前结果的最后一个删掉
// aab
// a ab
current.remove(current.size() - 1);
}
}
}
/**
判断是否为回文串，双指针
*/
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) {
return false;
}
}
return true;
}
}C++写法：
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result; // 存储结果
vector<string> current; // 当前路径
backtrack(s, 0, current, result); // 进入回溯
return result;
}
private:
/**
* 回溯函数
* @param s 字符串
* @param start 当前起始位置
* @param current 当前路径
* @param result 结果集
*/
void backtrack(const string& s, int start, vector<string>& current, vector<vector<string>>& result) {
// 如果已经遍历到字符串末尾，将当前路径加入结果集
if (start == s.length()) {
result.push_back(current);
return;
}
// 遍历所有可能的分割点
for (int end = start; end < s.length(); end++) {
// 判断当前子串是否为回文
if (isPalindrome(s, start, end)) {
// 如果是回文，加入当前路径
current.push_back(s.substr(start, end - start + 1));
// 继续递归处理剩余部分
backtrack(s, end + 1, current, result);
// 回溯，移除当前子串
current.pop_back();
}
}
}
/**
* 判断是否为回文串
* @param s 字符串
* @param left 左边界
* @param right 右边界
* @return 是否为回文
*/
bool isPalindrome(const string& s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--]) {
return false;
}
}
return true;
}
};运行时间
时间复杂度和空间复杂度
这里每次判断回文的时间是O(n)，而回溯的深度是O(n)，
所以总的时间复杂度大概是O()。
这样应该就能正确生成所有可能的分割方式。例如，对于输入"aab"，第一次循环start=0，end从0到2。当end=0时，子串是a，是回文。然后递归处理start=1。在递归调用中，start=1，end从1到2。当end=1时，子串是a，加入后递归处理start=2。此时，在start=2时，end只能是2，子串是b，加入后递归到start=3，此时将current加入结果。然后回溯，移除b，回到start=2的情况。此时循环结束，回溯到start=1的情况，此时移除a，接着end=2，判断子串ab是否是回文？显然不是，所以跳过。然后回到最初的循环，此时end=0的情况处理完毕，继续循环到end=1。此时子串是aa，是回文。加入后递归处理start=2。此时处理b，同样加入后得到结果。因此，两种分法都会被找到。
有没有优化的空间呢？比如预处理所有可能的子串是否是回文，这样在回溯时可以直接查询，而不用每次都计算。这可以用动态规划的方法预处理一个二维数组dp，其中dp[i][j]表示i到j是否是回文。预处理的时间是O()，然后每次判断是O(1)。
动态规划的预处理方法是怎么样的呢？比如，对于每个i和j，如果s[i]等于s[j]，并且中间的字符串也是回文（或者i和j之间的距离小于等于2），那么dp[i][j]为true。这样，可以提前计算出所有可能的回文子串。然后在回溯的时候，直接查询这个数组即可，提高效率。
那如何生成这个dp数组呢？初始化的时候，所有长度为1的子串都是回文。然后对于长度大于等于2的子串，根据状态转移方程处理。具体如下：
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int j = 1; j < n; j++) {
for (int i = 0; i < j; i++) {
if (s.charAt(i) != s.charAt(j)) {
dp[i][j] = false;
} else {
if (j - i + 1 <= 2) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
}
}或者，可以按长度来遍历，先处理长度为2的子串，然后长度3，直到n。或者像上面那样，外层循环是j，内层是i，从0到j-1。这样，可以确保在计算dp[i][j]的时候，dp[i+1][j-1]已经被计算过了。
不管怎样，预处理dp数组之后，回溯时可以直接使用dp[start][end]来判断是否是回文，这样每次判断都是O(1)，这样总的时间复杂度可以降低，虽然最坏情况下还是指数级的，但常数会更低。
至此，解法二已经呼之欲出了：
解法二：采用动态规划预处理+回溯
Java写法：
class Solution {
public List<List<String>> partition(String s) {
// 用于存储所有可能的分割方案
List<List<String>> result = new ArrayList<>();
// 字符串的长度
int n = s.length();
// dp[i][j] 表示 s 的子串 s[i...j] 是否为回文
boolean[][] dp = new boolean[n][n];
// 初始化：单个字符一定是回文
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 填充 dp 数组，判断所有可能的子串是否为回文
for (int j = 1; j < n; j++) { // j 是子串的结束位置
for (int i = 0; i < j; i++) { // i 是子串的起始位置
// 如果 s[i] == s[j]，则需要进一步判断内部子串是否为回文
if (s.charAt(i) == s.charAt(j)) {
// 如果子串长度 <= 2（即 i 和 j 相邻或相同），则一定是回文
// 否则，判断内部子串 s[i+1...j-1] 是否为回文dp[i + 1][j - 1]也就是去掉两端
if (j - i <= 2 || dp[i + 1][j - 1]) {
dp[i][j] = true;
}
} else {
// 如果 s[i] != s[j]，则 s[i...j] 不是回文
dp[i][j] = false;
}
}
}
// 使用回溯算法，找到所有可能的分割方案
backtrack(s, 0, new ArrayList<>(), result, dp);
// 返回结果
return result;
}
/**
* 回溯函数，用于寻找所有可能的分割方案
* @param s 原始字符串
* @param start 当前处理的起始位置
* @param current 当前的分割方案
* @param result 存储所有分割方案的结果集
* @param dp 动态规划数组，用于快速判断子串是否为回文
*/
private void backtrack(String s, int start, List<String> current, List<List<String>> result, boolean[][] dp) {
// 如果已经处理到字符串末尾，将当前分割方案加入结果集
if (start == s.length()) {
result.add(new ArrayList<>(current));
return;
}
// 遍历所有可能的分割点
for (int end = start; end < s.length(); end++) {
// 如果 s[start...end] 是回文
if (dp[start][end]) {
// 将当前回文子串加入当前分割方案
current.add(s.substring(start, end + 1));
// 递归处理剩余部分
backtrack(s, end + 1, current, result, dp);
// 回溯：移除当前回文子串，尝试其他分割点
current.remove(current.size() - 1);
}
}
}
}C++写法：
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<string>> partition(string s) {
// 用于存储所有可能的分割方案
vector<vector<string>> result;
// 字符串的长度
int n = s.length();
// dp[i][j] 表示 s 的子串 s[i...j] 是否为回文
vector<vector<bool>> dp(n, vector<bool>(n, false));
// 初始化：单个字符一定是回文
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 填充 dp 数组，判断所有可能的子串是否为回文
for (int j = 1; j < n; j++) { // j 是子串的结束位置
for (int i = 0; i < j; i++) { // i 是子串的起始位置
// 如果 s[i] == s[j]，则需要进一步判断内部子串是否为回文
if (s[i] == s[j]) {
// 如果子串长度 <= 2（即 i 和 j 相邻或相同），则一定是回文
// 否则，判断内部子串 s[i+1...j-1] 是否为回文
if (j - i <= 2 || dp[i + 1][j - 1]) {
dp[i][j] = true;
}
} else {
// 如果 s[i] != s[j]，则 s[i...j] 不是回文
dp[i][j] = false;
}
}
}
// 使用回溯算法，找到所有可能的分割方案
vector<string> current; // 当前的分割方案
backtrack(s, 0, current, result, dp);
// 返回结果
return result;
}
private:
/**
* 回溯函数，用于寻找所有可能的分割方案
* @param s 原始字符串
* @param start 当前处理的起始位置
* @param current 当前的分割方案
* @param result 存储所有分割方案的结果集
* @param dp 动态规划数组，用于快速判断子串是否为回文
*/
void backtrack(const string& s, int start, vector<string>& current, vector<vector<string>>& result, const vector<vector<bool>>& dp) {
// 如果已经处理到字符串末尾，将当前分割方案加入结果集
if (start == s.length()) {
result.push_back(current);
return;
}
// 遍历所有可能的分割点
for (int end = start; end < s.length(); end++) {
// 如果 s[start...end] 是回文
if (dp[start][end]) {
// 将当前回文子串加入当前分割方案
current.push_back(s.substr(start, end - start + 1));
// 递归处理剩余部分
backtrack(s, end + 1, current, result, dp);
// 回溯：移除当前回文子串，尝试其他分割点
current.pop_back();
}
}
}
};运行时间
时间复杂度和空间复杂度
总结
第一种操作已经不错了，但是在第二种方式这样预处理后的回溯应该效率更高。比如，判断回文的时间从O(n)变为O(1)，在测试用例数据量大的时候判断时会有优势。
反正，这两种方法都是可行的。选择哪一种取决于具体的输入规模。如果题目允许的话，预处理更好。