<span>【题解】力扣 131. 分割回文串</span>
题目来源
思路
方法一
dfs
以截取的字符子串是否符合条件，是否是回文串，来判断是否构成一条分支。
如果是回文串，就将这一子串添加到路径中，并开始下一轮搜索。
如果搜索的下标等于字符串长度，就代表搜索完了，将路径添加到答案中。
可以根据树形结构来理解dfs中的for循环
本题的树形结构是一颗多叉树，树形结构如下：
class Solution {
public List<List<String>> partition(String s) {
char[] ch = s.toCharArray();
int len = ch.length;
List<List<String>> res = new ArrayList();
Deque<String> path = new ArrayDeque();
dfs(ch, 0, len, path, res);
return res;
}
public void dfs(char[] ch, int index, int len, Deque<String> path, List<List<String>> res){
// 搜索完毕，添加到答案中并返回
if(index == len){
res.add(new ArrayList(path)); // new一个ArrayList，相当于复制一个path
return;
}
// 从下标开始，截取1个、2个、3个、...直到截取下标到字符串最后一个字母为止。
for(int i = index;i<len;i++){
// 判断是不是回文串，如果不是，就剪枝
if(!check(ch, index, i)){
continue;
}
// 直接截取字符串会消耗性能，String.substring(String str, int start, int end)，[start,end-1]。
// 所以用构造方法代替 new String(char[] ch, int index, int len); 从index开始构造长度为len的字符串
path.addLast(new String(ch, index, i+1-index));
dfs(ch, i+1, len, path, res);
path.removeLast(); // 回溯
}
}
// 判断回文串
public boolean check(char[] ch, int left, int right){
while(left < right){
if(ch[left] != ch[right]){
return false;
}
left++;
right--;
}
return true;
}
}
方法二
动态规划+dfs
在方法一中，我们在check方法里面输出每次检查的left指针和right指针，
public boolean check(char[] ch, int left, int right){
System.out.printf("%d %d\n",left, right);
while(left < right){
if(ch[left] != ch[right]){
return false;
}
left++;
right--;
}
return true;
}
/*
以s="aab"为例：
0 0
1 1
2 2
1 2
0 1
2 2（重复）
0 2
*/
会出现重复检查子串是不是回文串的情况，为了避免重复检查，我们使用动态规划来解决这个问题。
我们可以将所有的子串是否是回文，先提前用二维数组存起来。
定义dp子问题：dp[i][j]：从i到j的子串是否为回文。
dp[i][j]为真的情况：
i==j时，子串只有一个字符，肯定是回文j-1==i时，子串由两个字符组成，字符必须相同s[i] == s[j]j-1>i时，子串由两个以上的字符组成，s[i] == s[j]，且dp[i+1][j-1] == true即除去首尾字符的剩余子串也是回文子串
对于1、2、时base case，如下图地蓝色和粉色格子，不需要递推出来，第3点时状态转移方程。我们需要合适的扫描方向，才不会出现：求当前dp[i][j]时，它所以来的dp[i+1][j-1]还没求出来
class Solution {
char[] ch;
boolean[][] dp;
List<List<String>> res;
Deque<String> path;
public List<List<String>> partition(String s) {
ch = s.toCharArray();
int len = ch.length;
// 预处理
// 对所有有可能截取的字符串，判断它们是否构成回文串
dp = new boolean[len][len];
for(int right = 0;right<len;right++){
for(int left = 0;left<=right;left++){ // 这里left<=right的情况，相当于上文所说的第一点
if(left == right){
dp[left][right] = true;
}else if(right - left == 1 && ch[left] == ch[right]){
dp[left][right] = true;
}else if(right - left > 1 && ch[left] == ch[right] && dp[left+1][right-1]){
dp[left][right] = true;
}else{
dp[left][right] = false;
}
}
}
res = new ArrayList();
path = new ArrayDeque();
dfs(0, len);
return res;
}
public void dfs(int index, int len){
if(index == len){
res.add(new ArrayList(path));
return;
}
for(int i = index;i<len;i++){
if(dp[index][i]){
path.addLast(new String(ch, index, i+1-index));
dfs(i+1, len);
path.removeLast();
}
}
}
}
