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

原题链接:https://oj.leetcode.com/problems/palindrome-partitioning/

题目;给定一个字符串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