7.6分割回文串（LC131-M）
算法：
有很多分割结果，按照for循环去做肯定做不来
这个时候就要想到回溯！那就要画树！
画树
分割的画树过程其实和组合很像。
例如对于字符串aab：
- 组合问题：选取一个a之后，在ab中再去选取第二个，选取a之后b中再选取第三个.....。
- 切割问题：切割一个a之后，在ab中再去切割第二段，切割a之后在b再切割第三段.....。
回溯三部曲：
1.确定返回值和参数
返回值：void
参数：
string s 题目自带的
int startindex 确定每次递归从哪个字符开始切割
2.确定终止条件
切割到字符串最后，就是终止
startindex就是切割线：
startindex >= s.length()
并且要收集结果
3.单层递归逻辑：
子串怎么表示的？
答：[startindex, i]
i是这样定义的：
for (int i = startIndex; i < s.length(); i++)
收集结果：
若子串是回文（要定义一个新的函数，判断子串是否为回文），
将子串add入path，收集
若不是回文，continue，跳出该递归
递归：
注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1
backtracking (s, i+1)
回溯：
弹出本次已经添加的子串
path.removeLast()
判断回文子串
最后我们看一下回文子串要如何判断了，判断一个字符串是否是回文。
可以使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了。
调试过程：
第一次调试：
class Solution {//全局变量path和resultList<List<String>> result = new LinkedList<>();List<String> path = new LinkedList<>();public List<List<String>> partition(String s) {backtracking (s, 0);return result;}void backtracking (String s, int startindex){//终止条件，收集结果if (startindex >= s.length()){result.add(new LinkedList (path));return;}//单层递归逻辑//判断子串是否为回文if (isplalindrome (s, startindex, i)){//若是，加入pathpath.add (s[startindex, i]);}else {continue;}//递归backtracking (s, i+1);//回溯path.removeLast();}//判断回文plalindrome,左闭右闭boolean isplalindrome (String s, int start, int end){//双指针法for (int i, int j; i <= s.length(), j >=i; i++, j--){if (s[i] == s[j]) return true;return false;}}
}
原因：
1.path.add (s[startindex, i]);` 这一行存在语法错误。想要将子串添加到 `path` 列表中。为了修正这个问题，应该使用 `substring` 方法而不是方括号。修正后的代码应该是：path.add(s.substring(startIndex, i + 1));
在Java中，方括号主要用于数组的索引访问，而不用于提取子串（方括号是适用于python的，java不能用）。
对于字符串提取子串，可以使用`substring`方法，该方法接受起始索引和结束索引作为参数，以提取指定范围内的子串。[左闭右开）
String str = "Hello, World!";
String sub = str.substring(startIndex, endIndex); 在这里，`str`是要提取子串的字符串，`startIndex`是子串的起始索引，`endIndex`是子串的结束索引（不包括在内）。提取的子串将包括从`startIndex`到`endIndex-1`的字符。
因此，在您的代码中，`path.add(s.substring(startIndex, i + 1));`将会提取`s`字符串中从`startIndex`到`i`（包括`i`）的子串，并将其添加到`path`列表中。
2.`isPalindrome` 方法中的for循环存在几个语法错误。看起来您想要在for循环中声明和初始化多个变量，但是语法是不正确的。让我们进行以下更正：
for (int i = start, j = end; i <= j; i++, j--) { // ... (代码的其余部分)
} 在 Java 中，当在 for 循环中声明多个变量时，不需要在每个变量前都加上 `int`。
在 for 循环的初始化部分，只需要在第一个变量声明前加上类型，而后续的变量声明则只需要写变量名和初始值即可。
修改后：
原因：单层递归时忘记加for循环了
第二次调试：
原因：
string不能用方括号
应改为：
s.charAt(i) == s.charAt(j)第三次调试：
原因：把字符串本身也输出了。
主要问题在判断回文的逻辑上
（判断是否为xxx，一定要先判错！有错即错！）
当发现不是回文，就要立刻false；有不对的就不往下遍历了。一旦我们找到了一个不同的字符对，我们就可以确定这个字符串不是回文，因此可以立即返回 `false`。这样可以提前结束检查，因为一旦发现不匹配，就不需要继续向后检查。
我原来判断的是，先判断前后是否相等，若相等，则true。
假设字符串是 “abca”。如果我们在检查第一个和最后一个字符相等时就提前返回 `true`，那么我们会错误地认为 “abca” 是一个回文字符串，因为我们没有检查中间的字符。而且，当我们找到不同的字符时，就无法及时结束检查，而需要继续检查下去，这会降低算法的效率。
正确代码：
class Solution {//全局变量path和resultList<List<String>> result = new LinkedList<>();List<String> path = new LinkedList<>();public List<List<String>> partition(String s) {backtracking (s, 0);return result;}void backtracking (String s, int startindex){//终止条件，收集结果if (startindex >= s.length()){result.add(new LinkedList (path));return;}//单层递归逻辑//判断子串是否为回文for (int i=startindex; i<s.length();i++){ if (isplalindrome (s, startindex, i)){//若是，加入pathpath.add(s.substring(startindex, i+1));}else {continue;}//递归backtracking (s, i+1);//回溯path.removeLast();}}//判断回文plalindrome,左闭右闭boolean isplalindrome (String s, int start, int end){//双指针法for (int i=start, j=end; j >=i; i++, j--){if (s.charAt(i) != s.charAt(j)) return false; }return true;}
}