Palindrome Partitioning

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 List
  
   > partition(String s) {
    	List
   
    > res = new ArrayList<>(); List
    
      list = new ArrayList
     
      (); dfs(s, list, res); return res; } public void dfs(String s,List
      
        list,List
       
        > res){ if(s.length()<1){ //巨大错误：！！！ 这里必须注意不能写成res.add(list); 因为后面list会改变，导致最终res里面为空 res.add(new ArrayList
        
         (list)); return; } for(int i=0;i
          
          
 也可以换种写法思路一样实现有点细微差别：上面是每次改变字符串递归，下面写法是通过下标改变实现字符串变动。 
          
public List
           
            > partition(String s) {
        
		List
            
              item = new ArrayList
             
              (); List
              
               > res = new ArrayList<>(); if(s==null||s.length()==0) return res; dfs(s,0,item,res); return res; } public void dfs(String s, int start, List
               
                 item, List
                
                 > res){ if (start == s.length()){ res.add(new ArrayList
                 
                  (item)); return; } for (int i = start; i < s.length(); i++) { String str = s.substring(start, i+1); if (isPalindrome(str)) { item.add(str); dfs(s, i+1, item, res); item.remove(item.size() - 1); } } } public boolean isPalindrome(String s){ int low = 0; int high = s.length()-1; while(low < high){ if(s.charAt(low) != s.charAt(high)) return false; low++; high--; } return true; } }