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"]  ] 思路： 题目的要求是求所有的回文划分，因此一定是使用DFS（递归 + 回溯）模板。只需加入判断是否为回文的模块即可。

1 public class Solution { 2     /** 3      * @param s: A string 4      * @return: A list of lists of string 5      */ 6     public List
     
      
       > partition(String s) { 7         if (s == null || s.length() == 0) { 8             return null; 9         }10         List
       
        
         > result = new ArrayList<>();11         List
         
           path = new ArrayList<>();12         helper(s, result, path, 0);13         return result;14     }15     private boolean isPalindrome(String s) {16         int begin = 0;17         int end = s.length() - 1;18         while (begin < end) {19             if (s.charAt(begin) != s.charAt(end)) {20                 return false;21             }22             ++begin;23             --end;24         }25         return true;26     }27     private void helper(String s, List
          
           
            > result, List
            
              path, int pos) {28 if (pos == s.length()) {29 result.add(new ArrayList
             
              (path));30 return;31 }32 for (int i = pos; i < s.length(); i++) {33 String prefix = s.substring(pos, i + 1);34 if (!isPalindrome(prefix)) {35 continue;36 }37 path.add(prefix);38 helper(s, result, path, i + 1);39 path.remove(path.size() - 1);40 }41 }42 }