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

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

题意大致就是找出所有是回文的字符串分解方式。

解题思路：

我第一眼看过去，就只想到了可以用深度搜索的方式来解决，就是先从头分出一个字符情况时，剩下的可以怎么分；然后从头分出二个字符时，剩下的怎么分；依次类推…… 效率那是真的很低，但是估计是测试用例比较少，没有出现Time Limited的问题，只beats 1%。。。。

public class Solution {    public List
    
     
      > partition(String s) {		List
      
       
        > result = new ArrayList
        
         
          >(); List
          
            array = new ArrayList
           
            (); StringBuilder rest = new StringBuilder(s); partitionSubstring(result, array, rest); return result;    }  public void partitionSubstring(List
            
             
              > result, List
              
                array, StringBuilder rest){ if(rest.toString().length()==0){ List
               
                 temp = new ArrayList
                
                 (array); result.add(temp); return; } for(int i = 1; i <= rest.toString().length(); i++){ String s = rest.substring(0, i); if(isPalindrome(s)){ array.add(s); rest.delete(0, i); partitionSubstring(result, array, rest); rest.insert(0, s); array.remove(array.size()-1); } } } public boolean isPalindrome(String s){        return s.equals(new StringBuffer(s).reverse().toString());    }}
                
               
              
             
            
           
          
         
        
       
      
     
    

这么低的效率我也不能忍了，就只好去找别人的思路了。。。

果然，我就猜到是DP(动态规划)这个东西。我看到的作者是将是否是回文记录在了一个二维数组中，然后就不用像我一样每次都要调用方法判断了，然后也是用了深度搜索的方法。

动态规划这个东西我的理解就是要找好一个最优子结构，然后要设计好用什么表示和存储他，然后就可以使用了。

下面是经我修改提交后的代码：

//回文字符串划分//动态规划生成回文字符串数组//根据数组用深度搜索生成回文字符串的划分public class Solution {    //生成标志回文字符串的数组，partitioning_map[i][j]=1的话，表明：string[i..j]是一个回文字符串    void dp(String s, char [][] palindrome_map) {        for(int i=s.length()-1;i>=0;i--) {            for(int j=i;j
    
      array, List
     
      
       > result) {        if(begin==s.length()) {            result.add(array);            return;        }                for(int i=begin;i
       
        
          tmp = new ArrayList
         
          (array);                tmp.add(s.substring(begin,i+1));                dfs(s,i+1,palindrome_map,tmp, result);            }        }    }    public List
          
           
            > partition(String s) {        List
            
             
              > result = new ArrayList
              
               
                >();        List
                
                  array = new ArrayList
                 
                  ();        if(s==null||s.length()==0) {            result.add(array);            return result;        }        char [][] palindrome_map = new char[s.length()][s.length()];                dp(s, palindrome_map);        dfs(s,0,palindrome_map,array,result);        return result;    }}
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

原文地址：

beats 67%， 写的比我好多了。。。