Palindrome Partition

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

Return all possible palindrome partitioningof s.

For example, given s = 

"aab"

,

Return

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

中心思想：递归。如果当前的string和右边的string都能被partition成palindrome，那么将这个array加到结果中去。 教训：在继续recursion的时候，一定要将当前的tmp arraylistclone，不然recursion函数将会使用同一个arraylist。这时如果是iterative方法的估计会避免。 2014.8.10 update: 错误：在储存preresult的时候，要用List而不是List>，因为每一个solution都是一个单独的List> result 中的entry

// Palindrome Partitioning     public List>partition(String s) {         List> result = new ArrayList>();         helper(result, new ArrayList(), s);         return result;     }           void helper(List>result, List preResult, String s) {         if (s.isEmpty()) {             result.add(preResult);             return;         }                   for (int i = 1; i <= s.length(); i++) {             StringcurString = s.substring(0, i);             if(isPalindrome(curString)) {                 List anotherPreResult = newArrayList(preResult);                 anotherPreResult.add(curString);                 helper(result,anotherPreResult, s.substring(i));             }         }     }

    boolean isPalindrome(String s) {         int n = s.length();         for (int i = 0, j = n-1; i < j; i++, j--){             if(s.charAt(i) != s.charAt(j)) {                 return false;             }         }         return true;     }