LeetCode 132 Palindrome Partitioning II:
https://leetcode.com/discuss/76411/easiest-java-dp-solution-97-36%25
X. O(n) space
http://ninefu.github.io/blog/132-Palindrome-Partitioning-II/
https://discuss.leetcode.com/topic/2840/my-solution-does-not-need-a-table-for-palindrome-is-it-right-it-uses-only-o-n-space/11
each cut at i+j is calculated by scanning (i-j)'s minimum cut + 1 if s[i-j, i+j] is a palindrome
looking backwards of what he is doing, he is building the right cut K[i] for all i<n. aid K[n] is min(all valid palindrome(j,n) + K[j]).
My solution does not need a table for palindrome, is it right ? It uses only O(n) space
http://www.geeksforgeeks.org/dynamic-programming-set-17-palindrome-partitioning/
Time Complexity: O(n^2)
f(i) = min [ f(j)+1, j=0..i-1 and str[j:i] is palindrome
0, if str[0,i] is palindrome ]
http://www.acmerblog.com/palindrome-partitioning-ii-6148.html
isPal[i][j]表示字符串s的子串s[i...j]是否为回文串，cut[j]表示子串s[0...j]所需要的最小分割数。
http://www.programcreek.com/2014/04/leetcode-palindrome-partitioning-ii-java/
http://blog.csdn.net/ljphhj/article/details/22573983
int[] cuts = new int[len + 1]; //cuts数组，cuts[i] 表示 以 i 开头到len结尾的子串 要达到题意需要的最少切割数（这样子最终 cuts[0]就是我们要的结果）【初始化 cuts[i] = len - i, 因为最坏情况以 i 开头到len结尾的子串要切割数就是每个字符都切一次】
Time Complexity: O(n^3)
This problem is a variation of Matrix Chain Multiplication problem. If the string is palindrome, then we simply return 0. Else, like the Matrix Chain Multiplication problem, we try making cuts at all possible places, recursively calculate the cost for each cut and return the minimum value.
LeetCode – Palindrome Partitioning I
http://www.lifeincode.net/programming/leetcode-palindrome-partitioning-i-and-iijava/
DP+Recursion
First, use DP to build up a table for all palindrome substrings such that T[i][j] == true if s[i..j] is a palindrome.
Then generate all partitions using recursion.
To avoid duplicate results, only generate a new partition if hitting a palindrome.
Suppose s[0..i] is a palindrome. All partitions containing (starting with) this substring are
s[0..i] + all partions of s[i+1..s.len-1].
public List<List<String>> partition(String s) {
http://n00tc0d3r.blogspot.com/2013/05/palindrome-partitioning.html
The algorithm above involves redundant calculations in the recursions. Instead of using a recursion, we can calculate the partitions backwards and store all previous results.
So, we create a table for previous results such that preRes[i] contains all of the partitions of s[i..len-1].
boolean[][] isPalindrome = new boolean[s.length()][s.length()];
int[] T = new int[s.length() + 1];
int val = -1;
for (int i = T.length - 1; i >= 0; i--) {
T[i] = val;
val++;
}
for (int i = s.length() - 1; i >= 0; --i) {
for (int j = i; j < s.length(); ++j) {
if (s.charAt(i) == s.charAt(j)
&& (j - i < 2 || isPalindrome[i + 1][j - 1])) {
isPalindrome[i][j] = true;
T[i] = Math.min(T[i], 1 + T[j + 1]);
}
}
}
return T[0];
}
https://leetcode.com/discuss/33077/solved-shortest-path-algorithm-clear-and-straightforward
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
For example, “aba|b|bbabb|a|b|aba” is a palindrome partitioning of “ababbbabbababa”. Determine the fewest cuts needed for palindrome partitioning of a given string. For example, minimum 3 cuts are needed for “ababbbabbababa”. The three cuts are “a|babbbab|b|ababa”. If a string is palindrome, then minimum 0 cuts are needed. If a string of length n containing all different characters, then minimum n-1 cuts are needed."aab",Return
1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.https://leetcode.com/discuss/76411/easiest-java-dp-solution-97-36%25
cut[i]is the minimum ofcut[j - 1] + 1 (j <= i), if[j, i]is palindrome.- If
[j, i]is palindrome,[j + 1, i - 1]is palindrome, andc[j] == c[i].
The 2nd point reminds us of using dp (caching).
a b a | c c
j i
j-1 | [j, i] is palindrome
cut(j-1) + 1X. O(n) space
http://ninefu.github.io/blog/132-Palindrome-Partitioning-II/
https://discuss.leetcode.com/topic/2840/my-solution-does-not-need-a-table-for-palindrome-is-it-right-it-uses-only-o-n-space/11
each cut at i+j is calculated by scanning (i-j)'s minimum cut + 1 if s[i-j, i+j] is a palindrome
looking backwards of what he is doing, he is building the right cut K[i] for all i<n. aid K[n] is min(all valid palindrome(j,n) + K[j]).
My solution does not need a table for palindrome, is it right ? It uses only O(n) space
the i is a pivot, and if i-j ~ i+j is pal, then the i+j+1 could be updated by the val in i - j.
Then we move i to the n - 1 to make sure we iterate all situation (all kind of pal beforehand),
and as the author said, the everything k which is below i is fixed and correct, because it has already consider all the situation of pal below itself.
and as the author said, the everything k which is below i is fixed and correct, because it has already consider all the situation of pal below itself.
int minCut(string s) {
int n = s.size();
vector<int> cut(n+1, 0); // number of cuts for the first k characters
for (int i = 0; i <= n; i++) cut[i] = i-1;
for (int i = 0; i < n; i++) {
for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);
for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) // even length palindrome
cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
}
return cut[n];
} 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];
}http://www.geeksforgeeks.org/dynamic-programming-set-17-palindrome-partitioning/
If we finding all palindromic substring 1st and then we calculate minimum cut, time complexity will reduce to O(n2).
int minPalPartion(char *str) { // Get the length of the string int n = strlen(str); /* Create two arrays to build the solution in bottom up manner C[i] = Minimum number of cuts needed for palindrome partitioning of substring str[0..i] P[i][j] = true if substring str[i..j] is palindrome, else false Note that C[i] is 0 if P[0][i] is true */ int C[n]; bool P[n][n]; int i, j, k, L; // different looping variables // Every substring of length 1 is a palindrome for (i=0; i<n; i++) { P[i][i] = true; } /* L is substring length. Build the solution in bottom up manner by considering all substrings of length starting from 2 to n. */ for (L=2; L<=n; L++) { // For substring of length L, set different possible starting indexes for (i=0; i<n-L+1; i++) { j = i+L-1; // Set ending index // If L is 2, then we just need to compare two characters. Else // need to check two corner characters and value of P[i+1][j-1] if (L == 2) P[i][j] = (str[i] == str[j]); else P[i][j] = (str[i] == str[j]) && P[i+1][j-1]; } } for (i=0; i<n; i++) { if (P[0][i] == true) C[i] = 0; else { C[i] = INT_MAX; for(j=0;j<i;j++) { if(P[j+1][i] == true && 1+C[j]<C[i]) C[i]=1+C[j]; } } } // Return the min cut value for complete string. i.e., str[0..n-1] return C[n-1]; }http://yucoding.blogspot.com/2013/08/leetcode-question-133-palindrome.html
f(i) = min [ f(j)+1, j=0..i-1 and str[j:i] is palindrome
0, if str[0,i] is palindrome ]
http://www.acmerblog.com/palindrome-partitioning-ii-6148.html
isPal[i][j]表示字符串s的子串s[i...j]是否为回文串，cut[j]表示子串s[0...j]所需要的最小分割数。
http://www.programcreek.com/2014/04/leetcode-palindrome-partitioning-ii-java/
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]; }
http://blog.csdn.net/ljphhj/article/details/22573983
int[] cuts = new int[len + 1]; //cuts数组，cuts[i] 表示 以 i 开头到len结尾的子串 要达到题意需要的最少切割数（这样子最终 cuts[0]就是我们要的结果）【初始化 cuts[i] = len - i, 因为最坏情况以 i 开头到len结尾的子串要切割数就是每个字符都切一次】
Time Complexity: O(n^3)
// i is the starting index and j is the ending index. i must be passed as 0 and j as n-1
minPalPartion(str, i, j) = 0 if i == j. // When string is of length 1.
minPalPartion(str, i, j) = 0 if str[i..j] is palindrome.
// If none of the above conditions is true, then minPalPartion(str, i, j) can be
// calculated recursively using the following formula.
minPalPartion(str, i, j) = Min { minPalPartion(str, i, k) + 1 +
minPalPartion(str, k+1, j) }
where k varies from i to j-1
int minPalPartion(char *str) { // Get the length of the string int n = strlen(str); /* Create two arrays to build the solution in bottom up manner C[i][j] = Minimum number of cuts needed for palindrome partitioning of substring str[i..j] P[i][j] = true if substring str[i..j] is palindrome, else false Note that C[i][j] is 0 if P[i][j] is true */ int C[n][n]; bool P[n][n]; int i, j, k, L; // different looping variables // Every substring of length 1 is a palindrome for (i=0; i<n; i++) { P[i][i] = true; C[i][i] = 0; } /* L is substring length. Build the solution in bottom up manner by considering all substrings of length starting from 2 to n. The loop structure is same as Matrx Chain Multiplication problem ( See http://www.geeksforgeeks.org/archives/15553 )*/ for (L=2; L<=n; L++) { // For substring of length L, set different possible starting indexes for (i=0; i<n-L+1; i++) { j = i+L-1; // Set ending index // If L is 2, then we just need to compare two characters. Else // need to check two corner characters and value of P[i+1][j-1] if (L == 2) P[i][j] = (str[i] == str[j]); else P[i][j] = (str[i] == str[j]) && P[i+1][j-1]; // IF str[i..j] is palindrome, then C[i][j] is 0 if (P[i][j] == true) C[i][j] = 0; else { // Make a cut at every possible localtion starting from i to j, // and get the minimum cost cut. C[i][j] = INT_MAX; for (k=i; k<=j-1; k++) C[i][j] = min (C[i][j], C[i][k] + C[k+1][j]+1); } } } // Return the min cut value for complete string. i.e., str[0..n-1] return C[0][n-1]; }LeetCode – Palindrome Partitioning II (Java)
LeetCode – Palindrome Partitioning I
http://www.lifeincode.net/programming/leetcode-palindrome-partitioning-i-and-iijava/
DP+Recursion
First, use DP to build up a table for all palindrome substrings such that T[i][j] == true if s[i..j] is a palindrome.
Then generate all partitions using recursion.
To avoid duplicate results, only generate a new partition if hitting a palindrome.
Suppose s[0..i] is a palindrome. All partitions containing (starting with) this substring are
s[0..i] + all partions of s[i+1..s.len-1].
public List<List<String>> partition(String s) {
int n = s.length();
boolean[][] isPalindrome = new boolean[n][n];
for (int i = 0; i < n; i++)
isPalindrome[i][i] = true;
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
if (j - i < 2 || isPalindrome[i + 1][j - 1])
isPalindrome[i][j] = true;
}
}
}
List<List<String>>[] palindromes = (List<List<String>>[])Array.newInstance(List.class, n + 1);
palindromes[n] = (List)(new LinkedList<List<String>>());
List<String> emptyList = new LinkedList<>();
palindromes[n].add(emptyList);
for (int i = n - 1; i >= 0; i--) {
palindromes[i] = (List)(new LinkedList<List<String>>());
for (int j = i; j < n; j++) {
if (isPalindrome[i][j]) {
List<List<String>> lists = palindromes[j + 1];
String substring = s.substring(i, j + 1);
for (List<String> list : lists) {
List<String> newList = new LinkedList<>();
newList.add(substring);
newList.addAll(list);
palindromes[i].add(newList);
}
}
}
}
return palindromes[0];
}
Solution - DP+DPhttp://n00tc0d3r.blogspot.com/2013/05/palindrome-partitioning.html
The algorithm above involves redundant calculations in the recursions. Instead of using a recursion, we can calculate the partitions backwards and store all previous results.
So, we create a table for previous results such that preRes[i] contains all of the partitions of s[i..len-1].
public ArrayList<ArrayList<String>> partition(String s) {
// build up a table for palindrome substrings
boolean[][] T = palindromeTable(s);
// this map is used to store previous results
// preRes.get(i) is all partitions of s[i..len-1]
HashMap<Integer, ArrayList<ArrayList<String>>> preRes =
new HashMap<Integer, ArrayList<ArrayList<String>>>();
for (int i=s.length()-1; i>=0; --i) {
ArrayList<ArrayList<String>> partitions = new ArrayList<ArrayList<String>>();
for (int j=i; j<s.length(); ++j) {
if (T[i][j]) {
if (j+1 == n) {
ArrayList<String> pp = new ArrayList<String>();
pp.add(s.substring(i, j+1));
partitions.add(pp);
} else {
for (ArrayList<String> p : preRes.get(j+1)) {
ArrayList<String> pp = new ArrayList<String>();
pp.add(s.substring(i, j+1));
pp.addAll(p);
partitions.add(pp);
}
}
}
}
preRes.put(i, partitions);
}
return preRes.get(0);
} private boolean[][] palindromeTable(String s) {
boolean[][] T = new boolean[s.length()][s.length()];
// single-char word is a palindrome
for (int i=0; i<s.length(); ++i) T[i][i] = true;
// multi-char words
for (int i=1; i<s.length(); ++i) {
// even
int l = i-1, r = i;
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
T[l--][r++] = true;
}
// odd
l = i-1; r = i+1;
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
T[l--][r++] = true;
}
}
return T;
}
public ArrayList<ArrayList<String>> partition(String s) { ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); if (s == null || s.length() == 0) { return result; } ArrayList<String> partition = new ArrayList<String>(); addPalindrome(s, 0, partition, result); return result; } private void addPalindrome(String s, int start, ArrayList<String> partition, ArrayList<ArrayList<String>> result) { //stop condition if (start == s.length()) { ArrayList<String> temp = new ArrayList<String>(partition); result.add(temp); return; } for (int i = start + 1; i <= s.length(); i++) { String str = s.substring(start, i); if (isPalindrome(str)) { // should cache it partition.add(str); addPalindrome(s, i, partition, result); partition.remove(partition.size() - 1); } } } private boolean isPalindrome(String str) { int left = 0; int right = str.length() - 1; while (left < right) { if (str.charAt(left) != str.charAt(right)) { return false; } left++; right--; } return true; } |
Decompose into palindromic strings PalindromePartitioningMinCuts.java
public static int minCuts(String s) {boolean[][] isPalindrome = new boolean[s.length()][s.length()];
int[] T = new int[s.length() + 1];
int val = -1;
for (int i = T.length - 1; i >= 0; i--) {
T[i] = val;
val++;
}
for (int i = s.length() - 1; i >= 0; --i) {
for (int j = i; j < s.length(); ++j) {
if (s.charAt(i) == s.charAt(j)
&& (j - i < 2 || isPalindrome[i + 1][j - 1])) {
isPalindrome[i][j] = true;
T[i] = Math.min(T[i], 1 + T[j + 1]);
}
}
}
return T[0];
}
首先设置dp变量 cuts[len+1]。cuts[i]表示从第i位置到第len位置（包含，即[i, len])的切割数（第len位置为空）。
初始时，是len-i。比如给的例子aab，cuts[0]=3，就是最坏情况每一个字符都得切割：a|a|b|' '。cuts[1] = 2, 即从i=1位置开始，a|b|' '。
cuts[2] = 1 b|' '。cuts[3]=0,即第len位置，为空字符，不需要切割。
上面的这个cuts数组是用来帮助算最小cuts的。
还需要一个dp二维数组matrixs[i][j]表示字符串[i,j]从第i个位置（包含）到第j个位置（包含） 是否是回文。
如何判断字符串[i,j]是不是回文？
1. matrixs[i+1][j-1]是回文且 s.charAt(i) == s.charAt(j)。
2. i==j（i，j是用一个字符）
3. j=i+1（i，j相邻）且s.charAt(i) == s.charAt(j)
当字符串[i,j]是回文后，说明从第i个位置到字符串第len位置的最小cut数可以被更新了，
那么就是从j+1位置开始到第len位置的最小cut数加上[i,j]|[j+1,len - 1]中间的这一cut。
即，Math.min(cuts[i], cuts[j+1]+1)
最后返回cuts[0]-1。把多余加的那个对于第len位置的切割去掉，即为最终结果。
kind of weird
1 public int minCut(String s) {
2 int min = 0;
3 int len = s.length();
4 boolean[][] matrix = new boolean[len][len];
5 int cuts[] = new int[len+1];
6
7 if (s == null || s.length() == 0)
8 return min;
9
10 for (int i=0; i<len; ++i){
11 cuts[i] = len - i; //cut nums from i to len [i,len]
12 }
13
14 for (int i=len-1; i>=0; --i){
15 for (int j=i; j<len; ++j){
16 if ((s.charAt(i) == s.charAt(j) && (j-i<2))
17 || (s.charAt(i) == s.charAt(j) && matrix[i+1][j-1]))
18 {
19 matrix[i][j] = true;
20 cuts[i] = Math.min(cuts[i], cuts[j+1]+1);
21 }
22 }
23 }
24 min = cuts[0]-1;
25 return min;
26 }
http://www.jiuzhang.com/solutions/palindrome-partitioning-ii/2 int min = 0;
3 int len = s.length();
4 boolean[][] matrix = new boolean[len][len];
5 int cuts[] = new int[len+1];
6
7 if (s == null || s.length() == 0)
8 return min;
9
10 for (int i=0; i<len; ++i){
11 cuts[i] = len - i; //cut nums from i to len [i,len]
12 }
13
14 for (int i=len-1; i>=0; --i){
15 for (int j=i; j<len; ++j){
16 if ((s.charAt(i) == s.charAt(j) && (j-i<2))
17 || (s.charAt(i) == s.charAt(j) && matrix[i+1][j-1]))
18 {
19 matrix[i][j] = true;
20 cuts[i] = Math.min(cuts[i], cuts[j+1]+1);
21 }
22 }
23 }
24 min = cuts[0]-1;
25 return min;
26 }
https://leetcode.com/discuss/33077/solved-shortest-path-algorithm-clear-and-straightforward
1) Build the directed acyclic graph: if substring s[i, .., j] is a palindrome, then there is an edge from i to j+1. 2) Find the shortest path d from 0 to n. Then d - 1 is the mincut.
if substring s[i, .., j] is a palindrome, then there is an edge from i to j+1: why not from i to j?
By the notation s[i, ..., j], I mean the substring starts from index i and ends at index j (includes j).
When you found a palindrome s[i, ..., j] and try to put a cut to the right of s[j], the next palindrome to look at should starts at s[j+1], i.e., the next vertex to explore is j+1.
