131. 分割回文串

package leetcode;

import java.util.ArrayList;
import java.util.List;

public class demo_131 {
    public List<List<String>> partition(String s) {
        List<List<String>> list=new ArrayList<List<String>>();
        backtrack(list, new ArrayList<String>(), s);
        System.out.println(list);
        return list;
    }
    public void backtrack(List<List<String>> list,List<String> li,String s) {
        if(s.equals("")) {
            list.add(new ArrayList<String>(li));
        }
        else {
            for(int index=1;index<=s.length();index++) {
                //每次截取一定长度的子串
                String s1=s.substring(0,index);
                int low=0;
                int high=s1.length()-1;
                int flag=1;
                //判断子串是否为回文串
                while(low<high) {
                    if(s.charAt(low)!=s.charAt(high)) {
                        flag=0;
                        break;
                    }
                    low=low+1;
                    high=high-1;
                }
                //回溯剩余的子串
                if(flag==1) {
                    li.add(s1);
                    backtrack(list, li, s.substring(index,s.length()));
                    li.remove(li.size()-1);
                }
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        demo_131 d131 =new demo_131();
        String string="aabbc";
        d131.partition(string);
    }
}