Palindrome Partitioning -- LeetCode - c++编程基础

这道题是求一个字符串中回文子串的切割，并且输出切割结果，其实是Word Break II和Longest Palindromic Substring结合，该做的我们都做过了。首先我们根据Longest Palindromic Substring重大方法建立一个字典，得到字符串中的任意子串是不是回文串的字典，不熟悉的朋友可以先看看哈。接下来就跟Word Break II一样，根据字典的结果进行切割，然后按照循环处理递归子问题的方法，如果当前的子串满足回文条件，就递归处理字符串剩下的子串。如果到达终点就返回当前结果。算法的复杂度跟Word Break II一样，取决于结果的数量，最坏情况是指数量级的。代码如下：

public ArrayList
  
   > partition(String s) {
    ArrayList
   
    > res = new ArrayList
    
     >(); if(s==null || s.length()==0) return res; helper(s, getDict(s),0,new ArrayList
     
      (), res); return res; } private void helper(String s, boolean[][] dict, int start, ArrayList
      





        item, ArrayList
       
        > res) { if(start==s.length()) { res.add(new ArrayList
        
         (item)); return; } for(int i=start;i
         
          =0;i--) { for(int j=i;j
          
           同样，这里同Word Break II一样也可以使用动态规划的方法，但是要对所有中间结果进行存储，花费大量的空间，这里就不列举代码了。这道题扩展还有Palindrome Partitioning II，虽然求解的问题类似，但是因为一些细节的不同，复杂度会有很大的变化，有兴趣的朋友可以看看哈。