LeetCode100之分割回文串(131)--Java

标签：Java 切割递归 -- StringBuilder 131 字符串 path 回文

1.问题描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。

示例1

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例2

输入：s = "a"
输出：[["a"]]

提示

1 <= s.length <= 16
s 仅由小写英文字母组成

难度等级

中等

题目链接

分割回文串

2.解题思路

这道题要我们找出将一个字符串分割成回文串的所有可能，要解决这道题的前提条件是，我们要能判断一个字符串是否为回文串。所以我们可以先写一个判断是否为回文串的方法，方便我们后续调用来判断。

判断回文串其实很简单，取字符串长度的一半，从索引0开始遍历，每一个比较索引位置的字符与字符串长度-1-索引位置的字符是否相等，相等就继续比较，不相等就一定不是回文串，遍历能够完成执行结束，说明是回文串，返回true。

    //判断是否为回文串
    public boolean isPalindrome(String s){
        for(int i =0; i < s.length() / 2;i++){
            if(s.charAt(i) != s.charAt(s.length() - 1 - i)){
                return false;
            }
        }
        return true;
    }

接着，我们来分析一下怎么使用递归来实现字符串的切割。

首先我们要确定我们需要用到传入的参数，我们需要传入题目提供的字符串，本次方法要切割的索引位置，存储所有可能的情况的List集合，存储以当前切割方案已经切割出来的回文串List集合，还有一个用于提高频繁修改字符串效率的StringBuilder。

  public void backtrack(String s,int index,List<List<String>> data,List<String> path,StringBuilder sb)

然后，我们就可以来确定递归的结束条件了。如果要切割的索引等于字符串的长度，说明已经切割到了字符串的末尾，没有回文串可以切割了，将当前的方案存入存储所有方案的集合中，然后递归结束。

        //如果index等于s的长度,说明已经切割完整个字符串,递归结束
        if(s.length() == index){
            //添加新方案
            data.add(new ArrayList<>(path));
            return;
        }

接着，我们就可以来确定当前的递归逻辑。从传入的索引处开始遍历字符串，将每一次遍历的字符存入StringBuilder中，表示当前正切割一半的子串，同时判断当前这个子串是否已经是一个回文串了，如果是的话，将当前子串存入当前方案的List集合中，然后递归调用获取当前方案的所有子方案。需要注意的是，这里我们需要重新new 一个StringBuilder作为参数传入新方案，因为我们这里的一个StringBuilder就是一个回文串，我们已经在这个索引位置进行切割了，要寻找新的回文串。找到所有的子方案之后，要将传入的回文串移除，以便获取其他的方案。

        //遍历index到s末尾的字符，尝试切割每一个位置
        for(int i = index;i < s.length();i++){
            //添加字符
            sb.append(s.charAt(i));
            //判断当前的字符串是否为回文串，是的话，可以在此切割
            if(isPalindrome(sb.toString())){
                //加入当前已经构成回文串的字符串
                path.add(sb.toString());
                //递归获取在此处切割的所有子方案
                backtrack(s,i+1,data,path,new StringBuilder());
                //去除当前已经构成回文串的字符串,寻找其他可能的分割方案
                path.remove(path.size()-1);
            }
        }

最后，我们只要在主方法中调用一次我们写的递归方法，将最终的答案返回即可。

3.代码展示

class Solution {
    public List<List<String>> partition(String s) {
        //存储所有可能的方案
        List<List<String>> data = new ArrayList<>();
        //递归获取所有的方案
        backtrack(s,0,data,new ArrayList<>(),new StringBuilder());
        //返回结果
        return data;
    }
    //递归获取所有的方案
    public void backtrack(String s,int index,List<List<String>> data,List<String> path,StringBuilder sb){
        //如果index等于s的长度,说明已经切割完整个字符串,递归结束
        if(s.length() == index){
            //添加新方案
            data.add(new ArrayList<>(path));
            return;
        }
        //遍历index到s末尾的字符，尝试切割每一个位置
        for(int i = index;i < s.length();i++){
            //添加字符
            sb.append(s.charAt(i));
            //判断当前的字符串是否为回文串，是的话，可以在此切割
            if(isPalindrome(sb.toString())){
                //加入当前已经构成回文串的字符串
                path.add(sb.toString());
                //递归获取在此处切割的所有子方案
                backtrack(s,i+1,data,path,new StringBuilder());
                //去除当前已经构成回文串的字符串,寻找其他可能的分割方案
                path.remove(path.size()-1);
            }
        }
    }
    //判断是否为回文串
    public boolean isPalindrome(String s){
        for(int i =0; i < s.length() / 2;i++){
            if(s.charAt(i) != s.charAt(s.length() - 1 - i)){
                return false;
            }
        }
        return true;
    }
}

4.总结

这道题，其实不是很难，唯一和之前递归回溯题目不太一样的地方就是，之前的题目的StringBuilder是从头到尾都是同一个对象，而在这道题里面，一个StringBuilder就是一个回文串，每一次调用递归方法都要重新new 一个StringBuilder。ok，今天这道题就啰嗦到这里，祝大家刷题愉快~

标签：Java,切割,递归,--,StringBuilder,131,字符串,path,回文
From： https://blog.csdn.net/2301_79318558/article/details/145101220