2014
10-06

Palindrome Partitioning II-动态规划

Palindrome Partitioning II

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.

public class PalindromePartitioning {
public int minCut(String s) {
int n = s.length();
boolean isPal[][] = new boolean[n][n];
int cut[] = new int[n];
for (int j = 0; j < n; j++) {
cut[j] = j;
for (int i = 0; i <= j; i++) {

//如果子串 s[i...j]是回文串
if (s.charAt(i) == s.charAt(j)
&& (j - i <= 1 || isPal[i + 1][j - 1])) {
isPal[i][j] = true;
if (i > 0)
cut[j] = Math.min(cut[j], cut[i - 1] + 1);
else
cut[j] = 0; //如果 s[0...j]是回文串，则说明不需要切割
}
}
}
return cut[n - 1];
}

public static void main(String[] args) {
String s = "aabbcaac";
PalindromePartitioning2 pp = new PalindromePartitioning2();
System.out.println(pp.minCut(s));
}
}

1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish