LeetCode-131-分割回文串
131. 分割回文串
难度中等
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16-
s仅由小写英文字母组成
思路
题意问的是，切分字符串s，切出的每一个子串必须是回文串，请找出所有切分的可能。
我们用指针 start 尝试着去切，切出一个回文串，基于新的 start，继续往下切，直到 start 越界
每次基于当前的 start，可以选择不同的 i，切出 start 到 i 的子串，我们枚举出这些选项 i：
- 切出的子串满足回文，将它加入部分解 temp 数组，并继续往下切（递归）
- 切出的子串不是回文，跳过该选择，不落入递归，继续下一轮迭代
结合动态规划
其实，我们可以把所有子串是否回文，提前求出来，用二维数组存起来。回溯时，直接取 dp 数组中对应元素就好。
定义 dp 子问题：dp[i][j]：从 i 到 j 的子串是否回文。
dp[i][j]为真，罗列出所有的情况：
i == j时，子串只有一个字符，肯定回文
j-i == 1时，子串由两个字符组成，字符必须相同s[i] == s[j]
j-i > 1时，子串由两个以上字符组成，s[i] == s[j]，且dp[i+1][j-1]=true即除去首尾字符的剩余子串也是回文子串。
1、2 是 base case，如下图的蓝、粉格子，不需要递推出来，3 是状态转移方程。
看看状态转移的方向，如下图，帮助我们计算dp矩阵时选取扫描方向，合适的扫描方向，才不会出现：求当前dp[i][j]时，它所依赖的dp[i+1][j-1]还没求出来。
image-20210614123351632
class Solution {
public static List<List<String>> partition(String s) {
// dp[L][R] -> 是不是回文
boolean[][] dp = getdp(s.toCharArray());
LinkedList<String> path = new LinkedList<>();
List<List<String>> ans = new ArrayList<>();
process(s, 0, path, dp, ans);
return ans;
}
public static boolean[][] getdp(char[] str) {
int N = str.length;
boolean[][] dp = new boolean[N][N];
for (int i = 0; i < N - 1; i++) {
dp[i][i] = true;
dp[i][i + 1] = str[i] == str[i + 1];
}
dp[N - 1][N - 1] = true;
for (int j = 2; j < N; j++) {
int row = 0;
int col = j;
while (row < N && col < N) {
dp[row][col] = str[row] == str[col] && dp[row + 1][col - 1];
row++;
col++;
}
}
return dp;
}
// s 字符串
// s[0...index-1] 已经做过的决定，放入了path中
// 在index开始做属于这个位置的决定，
// index == s.len path之前做的决定（一种分割方法），放进总答案ans里
public static void process(String s, int index, LinkedList<String> path,
boolean[][] dp, List<List<String>> ans) {
if (index == s.length()) {
ans.add(copy(path));
} else {
for (int end = index; end < s.length(); end++) {
// index..index
// index..index+1
// index..index+2
// index..end
if (dp[index][end]) {
path.addLast(s.substring(index, end + 1));
process(s, end + 1, path, dp, ans);
path.pollLast();
}
}
}
}
public static List<String> copy(List<String> path) {
List<String> ans = new ArrayList<>();
for (String p : path) {
ans.add(p);
}
return ans;
}
}
image-20210614220547271
