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"]
  ]

题目;给定一个字符串s , 把s 分成每个子串都是回文串。

返回s 的所有可能的回文切分。

思路：根据对示例的结果的观察，发现需要两个list，一个用于放入所有的单个字符，一个用于放入第二次的切分结果。于是有了下面的程序，即现遍历一遍，将单个字符加入到list中去；再切分字符，判断是否是回文，如是，则加入到第二个list中去；最后返回结果。但是如下的方法总是在第二次的时候会漏掉单个字符。

	public static List
  
   > partition(String s) {
		List
   
    > list = new ArrayList
    
     >(); List
     
       li = new ArrayList
      
       (); int len = s.length(); if(len == 0) return list; for(int i=0;i
       
         li1 = new ArrayList
        
         (); boolean flag = false; for(int i=0;i
         
          
 按照如上的程序，会与正确结果插肩而过。不过正确结果重复了呀。
          
 
          
 
          
 
           
 
            
 
             
 Input:
 
             
"cdd"
 
            
 
            
 
             
 Output:
 
             
[["c","d","d"],["dd"]]
 
            
 
            
 
             
 Expected:
 
             
[["c","d","d"],["c","dd"]]
 
            
 
           
 
          
 下面是引用了网友[1]的解法，可以Accept.学习了。
          
 
          
 这个题目考虑用动态规划解题，关键在于构造一个解空间，确定S的任意子串S(i, j)是不是对称的。判断标准如下：
 1、如果i == j，则S(i, j)是对称的；
 2、如果j - i == 1 && S[i] == S[j]，则S(i, j)是对称的；
 3、如果j - i > 1 && S[i] == S[j] && S(i + 1, j - 1)是对称的，则S(i, j)也是对称的。
 在构造完这样的解空间后，就可以在O(1)时间内判定任意子串是不是对称的了。算法实现如下：
 
 
          
 
          
	public ArrayList
           
            > partition(String s) {
		ArrayList
            
             > ret = new ArrayList
             
              >(); ArrayList
              
                r = new ArrayList
               
                (); int length = s.length(); boolean[][] map = new boolean[length][length]; findPartition(s, 0, ret, r, map); return ret; } private void findPartition(String s, int start, ArrayList
                
                 > ret, ArrayList
                 
                   r, boolean[][] map) { int length = s.length(); if (start == length && r.size() != 0) { ArrayList
                  
                    clone = new ArrayList
                   
                    (r); ret.add(clone); } else { for (int j = start; j < length; j++) { if (start == j || (j - start > 1 && s.charAt(start) == s.charAt(j) && map[start + 1][j - 1]) || (j - start == 1 && s.charAt(start) == s.charAt(j))) { map[start][j] = true; r.add(s.substring(start, j + 1)); findPartition(s, j + 1, ret, r, map); r.remove(r.size() - 1); } } } }
                   
                  
                 
                
               
              
             
            
           
          
 
          
 
          
 
          
 
 
 
          
 [1] reference: http://www.blogjava.net/menglee/archive/2013/12/19/407778.html