【LeetCode】Palindrome Partitioning III

问题来源：Palindrome Partitioning

该问题简单来说就是给定一个字符串，将字符串分成多个部分，满足每一部分都是回文串，请输出所有可能的情况。

       该问题的难度比较大，很可能第一次遇到没有思路，这很正常。下面我们一点点分析，逐步理清思路。先不考虑所有的情况，针对一个符合条件的划分，每一部分都是一个回文子串，而且各部分的长度不固定。也即每一部分都是原始字符串的一个子串，且满足回文条件。所有的划分都满足上述条件，所以这就启发我们首先判断原始字符串的任意子串是否为回文子串。判断一个字符串是否为回文串最简单的方法是对字符串进行遍历。得到回文子串的结果之后我们该如何利用去获得所有可能的划分呢？此时，该问题就变为一个典型的深搜问题，问题的解空间就是所有可能划分的划分树，我们只需要遍历所有的分支直到叶节点，即为一个可能的划分。按照这个思路完成的代码如下：

[java] view plain copy print ?

1. public class Solution {  
2.     public ArrayList<ArrayList<String>> partition(String s) {  
3.         int[][] dp=new int[s.length()][s.length()];  
4.           
5.         ArrayList<ArrayList<String>> result=new ArrayList<ArrayList<String>>();  
6.         ArrayList<String> r=new ArrayList<String>();  
7.           
8.         for(int i=0;i<s.length();i++)  
9.         {  
10.             for(int j=i;j<s.length();j++)  
11.             {  
12.                 int k=0;  
13.                 for(;k<(j-i+1)/2;k++)  
14.                 {  
15.                     if(s.charAt(i+k)!=s.charAt(j-k)) break;  
16.                 }  
17.                   
18.                 if(k==(j-i+1)/2)  
19.                 {  
20.                     dp[i][j]=1;  
21.                 }  
22.             }  
23.         }  
24.           
25.         dfs(0,s,dp,r,result);  
26.           
27.         return result;  
28.     }  
29.       
30. void dfs(int i,String s,int[][] dp,ArrayList<String> r,ArrayList<ArrayList<String>> result)  
31.     {  
32.         if(i==s.length())  
33.         {  
34.             ArrayList<String> t=new ArrayList<String>(r);  
35.             Collections.reverse(t);  
36.             result.add(t);  
37.             return;  
38.         }  
39.           
40.         for(int j=i;j<s.length();j++)  
41.         {  
42.             if(dp[i][j]==1)  
43.             {  
44.                 r.add(0,s.substring(i,j+1));  
45.                 dfs(j+1,s,dp,r,result);  
46.                 r.remove(0);  
47.             }  
48.         }  
49.     }  
50. }  

上述代码看似比较复杂，但其实就两个简单的部分：判断子串是否为回文串，然后深搜遍历所有的划分。判断子串是否为回文串采用了最朴素的循环遍历，在该题通过了测试，但是在第二题中将会超时，后面还会提到。深搜函数最重要的参数是第一个i，用来表示从字符串的i位置开始求划分，如果i已经超过了字符串的长度就说明完成了划分，保存一个可能的结果。如果i没有到字符串末尾，则判断从i开始到哪些位置是回文串，保存该回文串，然后从下一个位置继续深搜。如此就可以获得所有的划分。

问题来源：Palindrome Partitioning II

该问题是问题I的变种，现在不求所有的划分，而只求分组个数最小的划分。

       重新思考算法，DFS超时一般的原因都是由于递归过程中的重复子问题导致重复计算，最典型的例子是斐波那契数列的计算，递归和非递归算法的运行效率完全是两个概念，貌似这个问题和斐波那契数列问题类似。

通过上面的调用树，我们可以知道上面的深搜确实存在重复计算的问题。但是为什么算法I就可以采用深搜完成呢？这是因为算法I要获得所有的划分，因而针对算法二是重复子问题的时候，它们在算法I中对应的是不同的划分，因而不会存在重复子问题。事实上，算法I的输入由于遍历整个解空间，给定的字符串都很短，最长的串也只是“eegiicgaeadbcfacfhifdbiehbgejcaeggcgbahfcajfhjjdgj”，深搜足以应对。

[java] view plain copy print ?

1. void dfs(int i,int parts,int len,int[][] dp,int[][] count)  
2.     {  
3.         if(count[i][parts]==1) return;  
4.           
5.         if(i==len)  
6.         {  
7.             if(parts<minParts)  
8.             {  
9.                 minParts=parts;  
10.             }  
11.             return;  
12.         }  
13.           
14.         count[i][parts]=1;  
15.           
16.         for(int j=len-1;j>=i;j--)  
17.         {  
18.             if(dp[i][j]==1&&parts<minParts)  
19.             {  
20.                 dfs(j+1,parts+1,len,dp,count);  
21.             }  
22.         }  
23.     }  

上述代码通过创建一个count数组用来表示之前的子问题是否已经计算过，如果计算过就不必再去深搜。但是很遗憾，上述代码居然还超时！！！当字符串为

“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa”时，算法超时。不过让人欣慰的一点是，在上一次优化中超时的字符串在备忘录方法中没有超时，很快就可以得到结果。针对上面的长字符串，也可以较快得到结果。但是还超时，就说明一开始的判断任意子串是否为回文子串的复杂度太高。这个问题不能通过单纯地修改深搜为DP解决。