leetcode打怪升级系列：回文分割 II（132）

     通过校内认识的一个google同学，知道了leetcode（http://leetcode.com/onlinejudge）这个IT面试，在线评测网站，同学建议做完leetcode的所有题目，且代码在30-50之间并保证质量，做题时严格控制时间。于是决定从现在起开始leetcode上打怪升级，今天做了第一个题目，叫回文分割，题目地址在这里http://leetcode.com/onlinejudge#question_132。下面说说我的解题过程.

 

   题目：Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

 

   这道题不禁又使我联想起算导DP上矩阵最小连乘次数那道题（已经思维定势了），于是自然而然的就用了那道题的算法，大致思路如下：

 

     假如字符串的长度为n，连续取从2到n之间（包括n）的子串，举个例子：字符串abcd，第一趟循环取长度为2的子串，于是就有ab,bc,cd,第二趟取长度为3的子串，于是就有abc,bcd,最后取长度为4的字串，即abcd，也许你会问取这些子串干什么，因为题目要求使得每个子串为回文的最少截取次数，该问题具有最优子结构特性。

 

       我们可以用反证法证明，假设原字符串分割最小次数的分割方式为 A1|A2|A3，Ai代表分割的子串，这个问题就变成分别求A1，A2，A3三个子串的最小分割次数，假设A1分割方式不是最小分割次数，那么一定存在一种分割方式使A1的分割次数最小，从而使得整个字符串的分割次数最小，这与原始命题矛盾，所以结论是要使原字符串的分割次数最小，那么子串的分割次数必须是最小的。

 

       这样，我们就把大问题化简成小问题，小问题相比更好解决。我用F[i][j]代表原字符串索引第i到j子串分割次数的最小值，那么DP的状态转移方程为：F[i][j]=min{F[i][k]+F[k+1][j]+1,i=<k<j},看到这里也许你还是不明白为什么要取这些子串。

 

       举一个最简单的例子，原始字符串ABC，其最小的分割次数为 ([Str]代表Str的最小分割次数)[A]+[BC]+1，[AB]+[C]+1,[ABC](自身是否是回文串，如果是则该串不用切割，分割次数为0)，这些分割方式的最小值，而[BC]=min{[B]+[C]+1,[BC]},[AB]=min{[A]+[B]+1,[AB]}，看到了吗，每种长度的子串都用到了。

下面是实现的Java代码：

              

public static int minCut(String s) {
		int len = s.length();
		int[][] F = new int[len][len];//定义二维数组表示状态转移方程
		for (int i = 0; i < len; i++) {
			F[i][i] = 0;
		}
		for (int k = 2; k <= len; k++) {//子串长度从2取到len
			for (int i = 0; i <= len - k; i++) {
				int min = Integer.MAX_VALUE;
				for (int j = i; j < i + k; j++) {//在k长度的子串中取最小值
					if (j == i) {
						int ss = i, ee = i + k - 1;
						if (s.charAt(ss) == s.charAt(ee)&& (ss + 1 == ee || F[ss + 1][ee - 1] == 0)) {//判断是否是回文串
							min = 0;
							break;
						}
					} else {
						if (F[i][j - 1] != 0) {
							continue;
						}
						min = Math.min(F[i][j - 1] + F[j][i + k - 1] + 1, min);
					}
				}
				F[i][i + k - 1] = min;
			}
		}
		return F[0][len - 1];

	}

 

     此算法的时间负责度可见为O（n3），所以只过了leetcode上该题的小数据，大数据一直有一个数据是TLE，所以下面我会给出一个时间复杂度为O（n2）的算法。

 

（时间太晚了，回宿舍了，明天继续）