回溯——131. 分割回文串
1 题目描述
- 分割回文串 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/palindrome-partitioning
2 题目示例
示例 1： 输入：s = “aab” 输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2： 输入：s = “a” 输出：[[“a”]]
3 题目提示
1 <= s.length <= 16 s 仅由小写英文字母组成
4 思路
方法一：回溯 + 动态规划预处理 由于需要求出字符串s的所有分割方案，因此我们考虑使用搜索＋回溯的方法枚举所有可能的分割方法并进行判断。 假设我们当前搜索到字符串的第i个字符，且s[0…i-1]位置的所有字符已经被分割成若干个回文串，并且分割结果被放入了答案数组ans中，那么我们就需要枚举下一个回文串的右边界j，使得s[i…j]是一个回文串。 因此，我们可以从i开始，从小到大依次枚举j。对于当前枚举的j值，我们使用双指针的方法判断s[i…j]是否为回文串:如果s[i…j]是回文串，那么就将其加入答案数组ans中，并以j＋1作为新的à进行下一层搜索，并在未来的回溯时将s[i…j]从ans中移除。 如果我们已经搜索完了字符串的最后一个字符，那么就找到了—种满足要求的分割方法。 复杂度分析 时间复杂度:o(n 2²)，其中n是字符串s的长度。在最坏情况下，s包含n个完全相同的字符，因此它的任意—种划分方法都满足要求。而长度为n的字符串的划分方案数为2n-1= o(2²)，每一种划分方法需要O(n)的时间求出对应的划分结果并放入答案，因此总时间复杂度为o(n·2²)。尽管动态规划预处理需要o(n²)的时间，但在渐进意义下小于O(n2²)，因此可以忽略。 ·空间复杂度:O(n²)，这里不计算返回答案占用的空间。数组f需要使用的空间为O(n2)，而在回溯的过程中，我们需要使用O(n)的栈空间以及O(n)的用来存储当前字符串分割方法的空间。由于O(n)在渐进意义下小于o(n²)，因此空间复杂度为O(n²)。
方法二：回溯 + 记忆化搜索 方法一中的动态规划预处理计算出了任意的s[i…j]是否为回文串，我们也可以将这—步改为记忆化搜索。 复杂度分析
- 时间复杂度:O(n ﹒ 2²)，其中n是字符串s的长度，与方法一相同。
- 空间复杂度:o(n²)，与方法—相同。
5 我的答案
方法一：回溯 + 动态规划预处理
class Solution {
boolean[][] f;
List<List<String>> ret = new ArrayList<List<String>>();
List<String> ans = new ArrayList<String>();
int n;
public List<List<String>> partition(String s) {
n = s.length();
f = new boolean[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(f[i], true);
}
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
}
}
dfs(s, 0);
return ret;
}
public void dfs(String s, int i) {
if (i == n) {
ret.add(new ArrayList<String>(ans));
return;
}
for (int j = i; j < n; ++j) {
if (f[i][j]) {
ans.add(s.substring(i, j + 1));
dfs(s, j + 1);
ans.remove(ans.size() - 1);
}
}
}
}方法二：回溯 + 记忆化搜索
class Solution {
int[][] f;
List<List<String>> ret = new ArrayList<List<String>>();
List<String> ans = new ArrayList<String>();
int n;
public List<List<String>> partition(String s) {
n = s.length();
f = new int[n][n];
dfs(s, 0);
return ret;
}
public void dfs(String s, int i) {
if (i == n) {
ret.add(new ArrayList<String>(ans));
return;
}
for (int j = i; j < n; ++j) {
if (isPalindrome(s, i, j) == 1) {
ans.add(s.substring(i, j + 1));
dfs(s, j + 1);
ans.remove(ans.size() - 1);
}
}
}
// 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
public int isPalindrome(String s, int i, int j) {
if (f[i][j] != 0) {
return f[i][j];
}
if (i >= j) {
f[i][j] = 1;
} else if (s.charAt(i) == s.charAt(j)) {
f[i][j] = isPalindrome(s, i + 1, j - 1);
} else {
f[i][j] = -1;
}
return f[i][j];
}
}