获得一个字符串的所有回文子串集合

桃扇骨 2022-05-22 02:14 126阅读 0赞

![这里写图片描述][70]

import java.util.ArrayList;
    public class Solution {
        //获得一个字符串的所有回文子串集合
        public ArrayList<ArrayList<String>> partition(String s) {
             ArrayList<ArrayList<String>>arr=new ArrayList<ArrayList<String>>();
             if(s==null||s.length()==0)
               return arr;
             ArrayList<String> list=new ArrayList<String>();
             dfs(0,s,list,arr);
             return arr;
        }
        //回溯法
        private void dfs(int index,String s,ArrayList<String> preList, ArrayList<ArrayList<String>>arr)
        {
            if(index==s.length()){
              arr.add(new ArrayList<String>(preList));
               return;
            }
            ArrayList<String> list = new ArrayList<String>(preList);
            for(int i=index;i!=s.length();i++){
               if(isHui(s,index,i))
               {
                   list.add(s.substring(index,i+1));
                   dfs(i+1,s,list,arr); //递归调用
                   list.remove(list.size()-1);
               }
            }
        }
        //判断是否为回文串
        private boolean isHui(String s,int start,int end){
            while(start<=end){
                if(s.charAt(start++)!=s.charAt(end--))
                {
                   return false;
                }
            }
            return true;  
        }
        public static void main(String[]args){
           System.out.println("Hello World！");
           String s="aaab";
           Solution sol=new Solution();
           System.out.println(sol.partition(s));
    
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220522/3fde3554a9494278bd91320b8ab0f3bb.png
[70 1]: /images/20220522/541d46d3ff2f49caa0657262738ee515.png