【题目】

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",

Return

[    ["aa","b"],    ["a","a","b"]  ]

【回溯】

public class Solution {    public ArrayList
     
      
       > partition(String s) {    	ArrayList
       
        
         > result = new ArrayList
         
          
           >(); ArrayList
           
             list = new ArrayList
            
             (); if (s == null || s.length() == 0) return result; calResult(result,list,s); return result; } /** * 推断一个字符串是否是回文字符串 */ private boolean isPalindrome(String str){ int i = 0; int j = str.length() - 1; while (i < j){ if (str.charAt(i) != str.charAt(j)){ return false; } i++; j--; } return true; } /** * 回溯 * @param result : 终于要的结果集 ArrayList
             
              
               > * @param list : 当前已经增加的集合 ArrayList
               
                 * @param str : 当前要处理的字符串 */ private void calResult(ArrayList
                
                 
                  > result , ArrayList
                  
                    list , String str) { //当处理到传入的字符串长度等于0,则这个集合list满足条件，增加到结果集中 if (str.length() == 0) result.add(new ArrayList
                   
                    (list)); int len = str.length(); //递归调用 //字符串由前往后，先推断str.substring(0, i)是否是回文字符串 //假设是的话，继续调用函数calResult，把str.substring(i)字符串传入做处理 for (int i=1; i<=len; ++i){ String subStr = str.substring(0, i); if (isPalindrome(subStr)){ list.add(subStr); String restSubStr = str.substring(i); calResult(result,list,restSubStr); list.remove(list.size()-1); } } }}