Palindrome Partitioning II.java

H
1524717518
tags: DP, Partition DP

给一个String s, 找出最少用多少cut, 使致 切割出的每一个substring, 都是palindrome

#### Partition DP
- Find minimum cut: 分割型DP
- dp[i]: 最少cut多少刀, 使得前 i 长度的string, 割出来都是palindrome
- 最终要得到 dp[n], 所以 int[n + 1]
- 移动切刀, 看在哪里切, index j in [0 ~ i]
- 考虑[j, i - 1] 是否是回文串, 如果是, 那么: dp[i]= min(dp[i], d[j] + 1).
- note: 估计遍历 j 的时候, 反过来遍历也可以.

#### 计算Palindrome的优化
- 利用palindrome的性质, 可以算出 boolean palindrome[i, j]的情况. 
- 找一个任意mid point:
- 1. 假设palindrome是奇数长度, 那么 mid 是单独的字符, 而两边的字符 [mid-1], [mid+1] 应该完全相等.
- 2. 假设palindrome是偶数长度, 那么 [mid] 和 [mid + 1] 这样位置的字符应该相等.
- 这样做出来 palindrome[i, j]: 从字符 i 到 字符 j 的 substring 是否是 palindrome
- 这样就给我们的问题合理降维, 目前是time: O(n^2). 
- 不然求一次palindrome, 就是n, 会变成O(n^3)

#### Previous Notes
- Double for loop 检查每种substring string (i~j). 若i,j相邻或者同点，那么肯定isPal；否则，i,j之间的（i+1, j-1）一定得isPal。
- 看上去，在检查i,j的时候，中间按的（i+1, j-1）怎么可能先知道？ 其实不然..在j慢慢长大的时候，所有的0~j的substring都检查过。所以isPal[i+1][j-1]一定是已经知道结果的。
- okay.那么假如以上任意一种情况成立，也就是说isPal[i][j] == true。那就要判断，切到第一层循环参数j的末尾点时，有多少种切法？
- 想法很顺：我们naturally会想到，把i之前的cut加上i~j之间发生的不就好了。
- 反正现在j不变，现在就看吧i定在哪里，cut[i - 1]是否更小/最小； 再在cut[i-1]基础上+1就完了。
- 当然，如果i==0, 而 i~j又是isPal,那没啥好谈的，不必切，0刀。
- 最终，刷到cut[s.length() - 1] 也就是最后一点。 return的理所应当。


```
/*
Given a string s, cut s into some substrings such that every substring is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Example
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
Tags Expand 
Dynamic Programming
*/

/*
Thoughts:
Find minimum?
Say dp[i] represents min # of cuts for string with length i.
Think about last index i: dp[i]'s min depends on if previous 1 or more indexes forms a palindrome:
dp[i] = Min(dp[i - 1], dp[i - 2], dp[i - 3], .... dp[i - x]) + 1, assuming [i-1, i) is palindrome.
Set up a j and let j = i - 1, j-- to try all options see if any [j, i-1] is palindrome.

Note:
dp[i] gives minimum # of palindromes.
We need cuts, so dp[i] - 1

O(n^2)
We optimized using a palindrome[][] to save all possible palindromes across [i,j]
*/
class Solution {
    public int minCut(String s) {
        if (s == null || s.length() <= 1) {
            return 0;
        }
        int len = s.length();
        int[] dp = new int[len + 1];
        boolean[][] palindrome = calcPalindrome(s.toCharArray());
        dp[0] = 0;

        for (int i = 1; i <= len; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) { // this works too: (int j = i - 1; j >= 0; j--)
                if (palindrome[j][i - 1]) { // check if [j , i - 1]
                    dp[i] = Math.min(dp[i], dp[j] + 1); // move cursor to j
                }
            }
        }
        return dp[len] - 1; // need cuts
    }

    /*
        Find if any [i,j] is palindrome.
        Start attempting from mid point, and expand to both side. Set true of is palindrome.
        For odd length: there will be a mid point, and expansion goes to both sides naturally.
        For even length: mid and mid+1 will be middle 2 indexes.
    */
    private boolean[][] calcPalindrome(char[] s) {
        int n = s.length;
        boolean[][] palindrome = new boolean[n][n];
        
        for (int mid = 0; mid < n; mid++) {
            // odd
            int i = mid, j = mid;
            while (i >= 0 && j < n && s[i] == s[j]) {
                palindrome[i][j] = true;
                i--;
                j++;
            }
            
            i = mid;
            j = mid + 1;
            while (i >= 0 && j < n && s[i] == s[j]) {
                palindrome[i][j] = true;
                i--;
                j++;
            }
        }
        return palindrome;
    }
}

/**
Print the min-cut solution
1. Record the index where the min-cut was taken.
2. Once the cuts: pi[i] is recorded, start from i = n to print the path
**/
class Solution {
    public int minCut(String s) {
        if (s == null || s.length() <= 1) {
            return 0;
        }
        int len = s.length();
        int[] dp = new int[len + 1];
        boolean[][] palindrome = calcPalindrome(s.toCharArray());
        dp[0] = 0;

        int[] pi = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (palindrome[j][i - 1]) { // check if [j , i - 1]
                    dp[i] = Math.min(dp[i], dp[j] + 1); // move cursor to j
                    if (dp[i] == dp[j] + 1) {
                        pi[i] = j;
                    }
                }
            }
        }
        // Print result
        int i = len;
        char[] arr = s.toCharArray();
        while (i != 0) {
            for (int j = pi[i]; j < i; j++) {
                System.out.print(arr[j]);
            }

            System.out.println();
            i = pi[i]; // move i to the cut position, backtrack
        }
        return dp[len] - 1; // need cuts
    }

    private boolean[][] calcPalindrome(char[] s) {
        int n = s.length;
        boolean[][] palindrome = new boolean[n][n];
        
        for (int mid = 0; mid < n; mid++) {
            // odd
            int i = mid, j = mid;
            while (i >= 0 && j < n && s[i] == s[j]) {
                palindrome[i][j] = true;
                i--;
                j++;
            }
            
            i = mid;
            j = mid + 1;
            while (i >= 0 && j < n && s[i] == s[j]) {
                palindrome[i][j] = true;
                i--;
                j++;
            }
        }
        return palindrome;
    }
}

/*
Previous notes
Thinking process:
DP problem.
Use a isPal to record if any [i ~ j] is Palindrome, true/false
    for any char s[i] and s[j], if s[i] == s[j], then need to check if [i + 1, j - 1] is Palindrome, which is just isPal[i + 1, j - 1].
Use cut[j] to record the minimal cut from char index [0 ~ j] 
    by default, cut[j] = j because the worst condition is cut j times at each charactor: none 2+ character palindrome, and split into individual chars.
    update cut[j] by comparing existing cut[j] and (cut[i - 1] + 1).
At the end, return cut[s.length() - 1].
 */
public class Solution {
    /**
     * @param s a string
     * @return an integer
     */
    public int minCut(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int length = s.length();
        boolean[][] isPal = new boolean[length][length];
        int[] cut = new int[length];
        for (int j = 0; j < length; j++) {
            cut[j] = j;
            for (int i = 0; i <= j; i++) {
                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;
                    }
                }
            }//end i_for
        }//end for j_for
        return cut[length - 1];
    }
};
```