题目：

给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。

返回s所有可能的回文串分割方案。

样例

给出 s = "aab"，返回

  [

    ["aa","b"],

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

  ]

解题：

这个题目不好搞啊，需要动态规划

，没有根据动态规划，也解决了，貌似是暴力解决

从下标pos开始，找到下标i使得 pos到i内是回文字符串，再从i+1开始，找到下一个回文串，这样一直找下去。。。

时间复杂度O(n²)

Java程序：

public class Solution {    /**     * @param s: A string     * @return: A list of lists of string     */    public ArrayList
      
       
        > partition(String s) {        // write your code here        ArrayList
        
         
          > result = new ArrayList
          
           
            >(); if(s==null) return result; ArrayList
            
              path = new ArrayList
             
              (); helper(s,path,0,result); return result; } private boolean isPalindrome(String s){ int beg = 0; int end = s.length() - 1; while(beg
              
                path,int pos,ArrayList
               
                
                 > result){ if(pos==s.length()){ result.add(new ArrayList
                 
                  (path)); return; } for(int i=pos+1;i<=s.length();i++){ String prefix = s.substring(pos,i); if(!isPalindrome(prefix)) continue; path.add(prefix); helper(s,path,i,result); path.remove(path.size()-1); } }}
                 
                
               
              
             
            
           
          
         
        
       
      

总耗时: 2017 ms

上面程序利用到的是深度优先遍历

DFS

(1) 判断是否结束

（2） for 循环取所有的子串

 2.1 判断是否是回文字符串

2.2 是加入，递归进行

2.3 不是，for循环下一位