LeetCode刷题笔记-回溯法-分割回文串

 1 //回文字符判断
 2     public boolean isPalindrome(String s,int start,int end){
 3         while(start<end){
 4             if(s.charAt(start)!=s.charAt(end))
 5                 return false;
 6             start++;
 7             end--;
 8         }
 9         return true;
10     }
11 
12     public List<List<String>> partition(String s) {
13         //求出所有子集
14         //判断是不是回文
15         List<List<String>> result = new ArrayList<>();
16         List<String> temp = new ArrayList<>();
17         part(result,temp,s,0);
18         return result;
19     }
20 
21     public void part(List<List<String>> result,List<String> temp,String s,int begin){
22         if (begin==s.length()){
23             result.add(new ArrayList(temp));  //一定要先申请内存，否则添加的是一个引用，返回结果为空。
24             return;  //处理完成一定要return！！！
25         }
26         for (int i=begin;i<s.length();i++){
27             if (isPalindrome(s,begin,i)){
28                 temp.add(s.substring(begin,i+1));
29                 part(result,temp,s,i+1);
30                 temp.remove(temp.size()-1);
31             }
34         }