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和result
    List<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)){
        //若是,加入path
        path.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和result
    List<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)){
        //若是,加入path
        path.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;
    }
}

时间空间复杂度: