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;}
}

时间空间复杂度：

•