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