Related: Leetcode 131 - Palindrome Partitioning
http://bangbingsyb.blogspot.com/2014/11/leetcode-palindrome-partitioning-i-ii.html
http://yucoding.blogspot.com/2013/08/leetcode-question-133-palindrome.html
X.https://leetcode.com/discuss/31828/my-accepted-java-solution
For Palindrome related problems, - DP and isPalindrome[][].
https://discuss.leetcode.com/topic/6414/dp-solution-some-thoughts
http://www.jiuzhang.com/solutions/palindrome-partitioning-ii/
https://segmentfault.com/a/1190000007660424
1、朴素动态规划法（无法通过大数据）：
int minCut(string s) {
int length = s.length();
if (length == 0) {
return 0;
}
vector<vector<int>> dp(length, vector<int>(length, INT_MAX));
for (int i = 0; i < length; ++i) {
dp[i][i] = 0;
}
for (int len = 2; len <= length; ++len) {
for (int start = 0; start + len <= length; ++start) {
int end = start + len - 1;
if (isPalindrome(s, start, end)) {
dp[start][end] = 0;
}
else {
for (int k = start; k < end; ++k) {
dp[start][end] = min(dp[start][end], dp[start][k] + dp[k + 1][end] + 1);
}
}
}
}
return dp[0][length - 1];
}
private:
bool isPalindrome(string& s, int left, int right) {
int i = left, j = right;
while(i < j) {
if(s[i] != s[j])
return false;
++i, --j;
}
return true;
}
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 =
Return
"aab",Return
1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
X. O(n) space - expand
public int minCut(String s) { if(s==null || s.length()<2){ return 0; } int n = s.length(); char[] t = s.toCharArray(); int[] dp = new int[n+1]; Arrays.fill(dp,Integer.MAX_VALUE); dp[0] = -1; int i = 0; while(i<n){ expand(t,dp,i,i); expand(t,dp,i,i+1); i++; } return dp[n]; } private void expand(char[] t,int[] dp,int i,int j){ while(i>=0 && j<t.length && t[i] == t[j]){ dp[j+1] = Math.min(dp[j+1],dp[i] + 1); i--;j++; } }
https://discuss.leetcode.com/topic/2840/my-solution-does-not-need-a-table-for-palindrome-is-it-right-it-uses-only-o-n-space/12
X. DP - Compute isPalindrom[][] and cuts[] at same time
public int minCut(String s) { if(s==null || s.length()<2){ return 0; } int n = s.length(); char[] t = s.toCharArray(); int[] dp = new int[n+1]; Arrays.fill(dp,Integer.MAX_VALUE); dp[0] = -1; int i = 0; while(i<n){ expand(t,dp,i,i); expand(t,dp,i,i+1); i++; } return dp[n]; } private void expand(char[] t,int[] dp,int i,int j){ while(i>=0 && j<t.length && t[i] == t[j]){ dp[j+1] = Math.min(dp[j+1],dp[i] + 1); i--;j++; } }
public int minCut(String s) {
int len = s.length();
int[] f = new int[len];
for (int i = 0; i < len; i++) {
f[i] = i;
}
for (int i = 0; i < len; i++) {
search(s, f, i, i);
search(s, f, i, i + 1);
}
// System.out.println(Arrays.toString(f));
return f[len - 1];
}
private void search(String s, int[] f, int left, int right) {
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
if (left == 0) {
// left == 0, substring(0, right+1) is palindrom, no cut needed
f[right] = 0;
} else {
f[right] = Math.min(f[right], f[left - 1] + 1);
}
left--;
right++;
}
}
public int minCut(String s) {
if(s.length()==0)return 0;
int[]c=new int[s.length()+1];
for(int i=0;i<s.length();i++)c[i]=Integer.MAX_VALUE;
c[s.length()]=-1;
for(int i=s.length()-1;i>=0;i--){
for(int a=i,b=i;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a--,b++) c[a]=Math.min(c[a],1+c[b+1]);
for(int a=i,b=i+1;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a--,b++) c[a]=Math.min(c[a],1+c[b+1]);
}
return c[0];
}
使用一个数组cut来记录回文串的分组，一个字符串最多可以分为每个字符一组，也就是n组(n为字符串长度)。初始化cut为1...n。
遍历每个字符作为中心，然后偏移量offset逐渐增加，判断中心两侧offset的字符是否相等，来判断是否回文。
这里注意回文有两种，一种形如"abcba"的奇数串，一种形如"abba"的偶数串，要分别处理。
当某个字符作为中心时，当前回文串的低位的前一位记录的是前一组的组别，+1之后得到当前回文串的组别，用+1之后的值和其本身的值比较，然后将较小值写入高位，使高位记录当前回文串的组别。
动态更新cut数组，最终可推导出最后一个分组，最后一个分组的组别号-1就是分割次数。
int minCut(char *s) { int len = strlen(s); int cut[len + 1]; for(int i = 0; i <= len; i++) cut[i] = i; for(int center = 0; center < len; center++) { for(int offset = 0; center - offset >= 0 && center + offset < len && s[center - offset] == s[center + offset]; offset++) cut[center + offset + 1] = MIN(cut[center + offset + 1], cut[center - offset] + 1); for(int offset = 0; center - offset - 1 >= 0 && center + offset < len && s[center - offset - 1] == s[center + offset]; offset++) cut[center + offset + 1] = MIN(cut[center + offset + 1], cut[center - offset - 1] + 1); } return cut[len] - 1; }
X. DP - Compute isPalindrom[][] and cuts[] at same time
http://www.cnblogs.com/grandyang/p/4271456.html
这道题是让找到把原字符串拆分成回文串的最小切割数，需要用动态规划Dynamic Programming来做，使用DP的核心是在于找出递推公式，之前有道地牢游戏Dungeon Game的题也是需要用DP来做，而那道题是二维DP来解，这道题由于只是拆分一个字符串，需要一个一维的递推公式，我们还是从后往前推，递推公式为：dp[i] = min(dp[i], 1+dp[j+1] ) i<=j <n，那么还有个问题，是否对于i到j之间的子字符串s[i][j]每次都判断一下是否是回文串，其实这个也可以用DP来简化，其DP递推公式为P[i][j] = s[i] == s[j] && P[i+1][j-1]，其中P[i][j] = true if [i,j]为回文
http://happycoding2010.blogspot.com/2015/10/leetcode-132-palindrome-partitioning-ii.html
https://discuss.leetcode.com/topic/32575/easiest-java-dp-solution-97-36
这道题是让找到把原字符串拆分成回文串的最小切割数，需要用动态规划Dynamic Programming来做，使用DP的核心是在于找出递推公式，之前有道地牢游戏Dungeon Game的题也是需要用DP来做，而那道题是二维DP来解，这道题由于只是拆分一个字符串，需要一个一维的递推公式，我们还是从后往前推，递推公式为：dp[i] = min(dp[i], 1+dp[j+1] ) i<=j <n，那么还有个问题，是否对于i到j之间的子字符串s[i][j]每次都判断一下是否是回文串，其实这个也可以用DP来简化，其DP递推公式为P[i][j] = s[i] == s[j] && P[i+1][j-1]，其中P[i][j] = true if [i,j]为回文
http://happycoding2010.blogspot.com/2015/10/leetcode-132-palindrome-partitioning-ii.html
https://discuss.leetcode.com/topic/32575/easiest-java-dp-solution-97-36
Use DP. dp[i][j] store if s[i..j] is palindrome or not. res[j] is the min cut of s[0..j]. In the loop, keep update dp[i][j] matrix and res[j] array. The complexity is O(N^2).
public int minCut(String s) {
int n=s.length();
char[] c=s.toCharArray();
boolean[][] dp=new boolean[n][n];
int[] res=new int[n];
for (int j=0; j<n; j++) {
res[j]=Integer.MAX_VALUE;
for (int i=j; i>=0; i--) {
dp[i][j]=i==j || (c[i]==c[j] && (i+1>=j-1 || dp[i+1][j-1]));
if (dp[i][j]) {
int cut=(i==0)?0:res[i-1]+1;
res[j]=Math.min(res[j],cut);
}
}
}
return res[n-1];
} public int minCut(String s) { int n = s.length(); boolean dp[][] = new boolean[n][n]; int cut[] = new int[n]; for (int j = 0; j < n; j++) { cut[j] = j; //set maximum # of cut for (int i = 0; i <= j; i++) { if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i+1][j-1])) { dp[i][j] = true; // if need to cut, add 1 to the previous cut[i-1] if (i > 0){ cut[j] = Math.min(cut[j], cut[i-1] + 1); }else{ // if [0...j] is palindrome, no need to cut cut[j] = 0; } } } } return cut[n-1]; }
- pal[i][j] , which is whether s[i..j] forms a pal
- d[i], which is the minCut for s[i..n-1]
Once we comes to a pal[i][j]==true:
- if j==n-1, the string s[i..n-1] is a Pal, minCut is 0, d[i]=0;
- else: the current cut num (first cut s[i..j] and then cut the rest s[j+1...n-1]) is 1+d[j+1], compare it to the exisiting minCut num d[i], repalce if smaller.
d[0] is the answer.
int minCut(string s) {
if(s.empty()) return 0;
int n = s.size();
vector<vector<bool>> pal(n,vector<bool>(n,false));
vector<int> d(n);
for(int i=n-1;i>=0;i--)
{
d[i]=n-i-1;
for(int j=i;j<n;j++)
{
if(s[i]==s[j] && (j-i<2 || pal[i+1][j-1]))
{
pal[i][j]=true;
if(j==n-1)
d[i]=0;
else if(d[j+1]+1<d[i])
d[i]=d[j+1]+1;
}
}
}
return d[0];
}
X. DP - Compute isPalindrom[][] then cuts[]
public int minCut(String s) { if(s == null || s.isEmpty()) return 0; // Building a dict boolean[][] dict = buildDict(s); // result[i] means from s[0,i], the min cut int[] result = new int[s.length() + 1]; result[0] = 0; for (int i = 0 ; i < s.length() ; i ++) { result[i + 1] = i + 1; // max cut: single char cut for (int j = 0 ; j <= i ; j ++) { if (dict[j][i]) { result[i + 1] = Math.min(result[i + 1], result[j] + 1); } } } return result[result.length - 1] - 1; } // dict[i][j] means substring(i, j + 1) is palin // dict(i, j) = char[i] == char[j] && dict(i + 1, j - 1) // So i starts from s.length to 0 // j starts from i to s.length private boolean[][] buildDict(String s) { int len = s.length(); boolean[][] dict = new boolean[len][len]; for (int i = len - 1 ; i >= 0 ; i --) { for (int j = i ; j < len ; j ++) { if (i == j) dict[i][j] = true; else if(i + 1 == j) dict[i][j] = s.charAt(i) == s.charAt(j); else dict[i][j] = s.charAt(i) == s.charAt(j) && dict[i + 1][j - 1]; } } return dict; }http://yucoding.blogspot.com/2013/08/leetcode-question-133-palindrome.html
X.https://leetcode.com/discuss/31828/my-accepted-java-solution
So my thought process was go through the string, char by char starting from the left. The current character would be the center of the palindrome and expand as much as I can. After it ceases to be a palindrome (e.g no longer matching end chars or reached the boundary of the string), the cost would be "1 + the cost of the substring I already processed to the left of the current palindrome I am on". I compare this cost under the index of the last char of my current palindrome. If it is less than what was previously recorded, the I record this new cost.
For example, let's take 'abb':
- Start with 'a'. Obviously a cost of 0 (base case)
- Now we go to 'b' (index 1). Since we haven't visited 'b', let's assign an initial cost to it, which is 1 + cost[0]. So cost[1] = 0+1 = 1. This makes sense since you only need a 1 cut to get two palindromes: 'a' and 'b'
- Let's try to expand 'b'
- 'ab': It's not a palindrome so do nothing
- 'abb': Not a palindrome either
After expansion, cost[1] remains 1.
- Now we go to 'b' (index 2). Initial cost[2] = cost[1]+1 = 2. Expanding...
- 'bb': Hey, a palindrome! So I will compute a cost of cost[0]+1 = 1 (remember "1 + cost of substring to the left...). Is 1 less than what I initially have in cost[2]? Yup, it is. So I record it: cost[2] = 1
After expansion, cost[2] was changed from 2 to 1, and rightfully so because that is the minimum cut we can do to get all substrings as palindromes: 'a' and 'bb'.
Another example but we'll go faster this time: 'xccx'
- 'x': cost[0] = 0. Base case.
- 'c' (index 1): Init cost[1] = 1. Expanding...
- 'xc': Nope
- 'xcc': Nope
- 'c': Init cost[2] = 2. Expanding...
- 'cc->xccx': Yes. Since we reached start of string, this is a base case. So new cost = 0. Is 0 > cost[3] = Integer.MAX_VALUE? Yes, so cost[3] = 0
- 'ccx': Nope
- 'x': Since cost[3] was previously entered a cost, we don't need to init. Expanding...
- 'cx': Nope
- Cost to cut entire string: cost[3] = 0
So there you go. With this method, you are assured that remaining substring (or 'previous state') to the left of the current palindrome is the minimum at that point because you already computed it earlier. You just need to +1 to the cost and see if you have a new minimum cost for the state you are currently in (the last character of the current palindrome).
int[] cost;
public int minCut(String s) {
if (s == null || s.length() < 2) return 0;
int N = s.length();
cost = new int[N];
for (int i = 0; i < N; i++)
cost[i] = Integer.MAX_VALUE;
cut(s);
return cost[N-1];
}
private void cut (String s) {
if (s.length() > 0) cost[0] = 0;
if (s.length() > 1) cost[1] = s.charAt(1) == s.charAt(0) ? 0 : 1;
int k = 0, l = 0, ni = 0;
for (int i = 2; i < s.length(); i++) {
if (cost[i] == Integer.MAX_VALUE) cost[i] = cost[i-1]+1;
for (int j = 1; j <= 2; j++) {
for (k = i-j, l = i;
k >= 0 && l <= s.length()-1 && s.charAt(k) == s.charAt(l);
k--, l++) {
int c = k == 0 ? 0 : cost[k-1]+1;
if (cost[l] > c) cost[l] = c;
}
}
}
}For Palindrome related problems, - DP and isPalindrome[][].
https://discuss.leetcode.com/topic/6414/dp-solution-some-thoughts
- return the mininum cut of the partition s => optimization => DP
- try to divide & conqure =>
public int minCutRecur(String s){
int n = s.length;
int n = s.length;
//base case
if(s < 2 || isPalindr(s)) return 0;
int min = n - 1;
for(int i = 1; i <= n - 1; i++){
if(isPalindr(s)){
min = Math.min(min, 1 + minCutRecur(s.substring(i)));
}
}
return min;
}
However, sub problem overlapped (are not independent with each other).
- Use DP to build the solution from bottom up.public int minCut(String s) {
int n = s.length();boolean[][] isPalindr = new boolean[n + 1][n + 1]; //isPalindr[i][j] = true means s[i:j) is a valid palindrome int[] dp = new int[n + 1]; //dp[i] means the minCut for s[0:i) to be partitioned for(int i = 0; i <= n; i++) dp[i] = i - 1;//initialize the value for each dp state. for(int i = 2; i <= n; i++){ for(int j = i - 1; j >= 0; j--){ //if(isPalindr[j][i]){ if(s.charAt(i - 1) == s.charAt(j) && (i - 1 - j < 2 || isPalindr[j + 1][i - 1])){ isPalindr[j][i] = true; dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n];}
Several optimizations include:
- No need to check if a string is a palindrome or not inside the loop by adjusting the order of getting of solution of the sub problems.
- assign dp[0] to be -1 so that when s[0:i) is a palindrome by itself, dp[i] is 0. This is for the consistency of the code.
The time complexity and the space complexity are both O(n ^ 2).
http://www.jiuzhang.com/solutions/palindrome-partitioning-ii/
https://segmentfault.com/a/1190000007660424
用cuts[i]表示当前位置最少需要切几次使每个部分都是回文。如果s(j,i)这部分是回文，就有cuts[i] = cuts[j-1] + 1。
现在我们需要做的就是对于已经搜索并确定的回文部分，用一个二维数组来表示。matrix[j] [i]表示j到i这部分是回文。
如果s.charAt(i) == s.charAt(j) && isPalindrome[j+1] [i-1]是回文，则不需重复该部分的搜索。isPalindrome[j] [i]也是回文。
现在我们需要做的就是对于已经搜索并确定的回文部分，用一个二维数组来表示。matrix[j] [i]表示j到i这部分是回文。
如果s.charAt(i) == s.charAt(j) && isPalindrome[j+1] [i-1]是回文，则不需重复该部分的搜索。isPalindrome[j] [i]也是回文。
以"abcccba"为例：
i不断向后扫描， j从头开始知道i(包含i).
i=3即第二个c那里，j走到2, c[i] == c[j] == 'c' && i - j = 1 < 2， 填表，求最值。
i=4即第三个c那里，j走到2, c[i] == c[j] == 'c' && isPalindrome(2+1,4-1), 填表，求最值。
i=5即第二个b那里，j走到1, c[i] == c[j] == 'b' && isPalindrome(1+1,5-1)即“ccc“， 填表，求最值。
使用isPalindrome的好处就是可以O(1)的时间，也就是判断头尾就可以确定回文。不需要依次检查中间部分。
X. https://blog.csdn.net/magicbean2/article/details/71158084i不断向后扫描， j从头开始知道i(包含i).
i=3即第二个c那里，j走到2, c[i] == c[j] == 'c' && i - j = 1 < 2， 填表，求最值。
i=4即第三个c那里，j走到2, c[i] == c[j] == 'c' && isPalindrome(2+1,4-1), 填表，求最值。
i=5即第二个b那里，j走到1, c[i] == c[j] == 'b' && isPalindrome(1+1,5-1)即“ccc“， 填表，求最值。
使用isPalindrome的好处就是可以O(1)的时间，也就是判断头尾就可以确定回文。不需要依次检查中间部分。
1、朴素动态规划法（无法通过大数据）：
int minCut(string s) {
int length = s.length();
if (length == 0) {
return 0;
}
vector<vector<int>> dp(length, vector<int>(length, INT_MAX));
for (int i = 0; i < length; ++i) {
dp[i][i] = 0;
}
for (int len = 2; len <= length; ++len) {
for (int start = 0; start + len <= length; ++start) {
int end = start + len - 1;
if (isPalindrome(s, start, end)) {
dp[start][end] = 0;
}
else {
for (int k = start; k < end; ++k) {
dp[start][end] = min(dp[start][end], dp[start][k] + dp[k + 1][end] + 1);
}
}
}
}
return dp[0][length - 1];
}
private:
bool isPalindrome(string& s, int left, int right) {
int i = left, j = right;
while(i < j) {
if(s[i] != s[j])
return false;
++i, --j;
}
return true;
}
