## Sunday, April 10, 2016

### LeetCode 132 - Palindrome Partitioning II

Related: Leetcode 131 - Palindrome Partitioning
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.
X. O(n) space
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
``````  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];
}``````
https://github.com/liguangsheng/leetcode/blob/master/132-Palindrome-Partitioning-II.MD

```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
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];
}```

1. pal[i][j] , which is whether s[i..j] forms a pal
2. 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.
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://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
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':
• 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
1. return the mininum cut of the partition s => optimization => DP
2. try to divide & conqure =>
public int minCutRecur(String s){
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).
1. 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:
1. 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.
2. 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

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“， 填表，求最值。