Leetcode - Palindrome Partition 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.

[balabala] 这道题目的直接思路是利用Palindrome Partition的思路，利用isPalin[i][j] 递归求解，算法复杂度是O(N^N)，果断超时。进一步优化，保存一个cut[][]数组，其中cut[i][j] 表示s[i,j] 对应子串的min cuts，递推式见代码，时间复杂度是O(N^3)，仍然超时。最终O(N^2)的版本是一年前网上找的答案，未记录出处。不知道大神脑袋瓜怎么运转的，我能理解正确性，但想不通如何得到这种优化思路的。method3是直接参考的，method4我就反了个求解顺序，原理同method3一样，若是自己想估计会写成method4的样子。貌似自己该多练习逆向思考。method3 和 method4中dp数组多开了一个，并且每个元素比真实值多1，这是个编码技巧，可以避免for循环中判断边界条件，一开始自己不能体会作者用意，dp数组不多开元素保持真实值，会得到wrong answer，带进代码debug下就能理解了。

 

public class Solution {
    // Method 5: 重做时自己的写法
    public int minCut(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int n = s.length();
        boolean[][] isPalin = new boolean[n][n];
        for (int i = 0; i < n - 1; i++) {
            isPalin[i][i] = true;
            isPalin[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }
        isPalin[n - 1][n - 1] = true;
        for (int l = 3; l <= n; l++) {
            for (int i = 0; i + l <= n; i++) {
                int j = i + l - 1;
                isPalin[i][j] = s.charAt(i) == s.charAt(j) && isPalin[i + 1][j - 1];
            }
        }
        if (isPalin[0][n - 1])
            return 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            if (!isPalin[0][i]) {
                dp[i] = n;
                for (int j = 0; j < i; j++) {
                    if (isPalin[j + 1][i])
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }
    // dp[i]:s.substring(0, i)需要的min cuts
    public int minCut(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int n = s.length();
        boolean[][] isPalin = new boolean[n][n];
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++)
            dp[i] = i;
        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j) && (i - j < 2 || isPalin[i - 1][j + 1])) {
                    isPalin[i][j] = true;
                    dp[i + 1] = Math.min(dp[i + 1], dp[j] + 1);
                }
            }
        }
        return dp[n] - 1;
    }
    
    // O(N^2)
    // dp[i]: s.substring(i, n) 需要的min cuts
    // dp[i] = min(dp[j] + 1), j > i
    // dp数组多加个元素的好处是dp[i] = Math.min(dp[i], dp[j + 1] + 1); 这一行不需要对下标进行检查
    public int minCut3(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int n = s.length();
        boolean[][] isPalin = new boolean[n][n];
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++)
            dp[i] = n - i;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || isPalin[i + 1][j - 1])) {
                    isPalin[i][j] = true;
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0] - 1;
    }
    
    // O(N^3)
    public int minCut2(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int[][] cut = new int[n][n];
        for (int i = 0; i < n; i++)
            dp[i][i] = true;
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                cut[i][i + 1] = 0;
            } else {
                dp[i][i + 1] = false;
                cut[i][i + 1] = 1;
            }
        }
        
        int j = 0;
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                j = i + len - 1;
                dp[i][j] = s.charAt(i) == s.charAt(j) ? dp[i + 1][j - 1] : false;
                if (dp[i][j]) {
                    cut[i][j] = 0;
                } else {
                    cut[i][j] = n;
                    for (int k = i; k < j; k++) {
                        cut[i][j] = Math.min(cut[i][j], cut[i][k] + cut[k + 1][j] + 1);
                    }
                }
            }
        }
        return cut[0][n - 1];
    }
    
    //O(N!)
    public int minCut1(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++)
            dp[i][i] = true;
        for (int i = 0; i < n - 1; i++)
            dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? true : false;
        int j = 0;
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                j = i + len - 1;
                dp[i][j] = s.charAt(i) == s.charAt(j) ? dp[i + 1][j - 1] : false;
            }
        }
        return getMinCut(s, 0, dp);
    }
    
    private int getMinCut (String s, int start, boolean[][] dp) {
        int n = s.length();
        if (start == n || dp[start][n - 1])
            return 0;
        
        int min = n - start;
        for (int i = start; i < n - 1; i++) {
            if (dp[start][i]) {
                min = Math.min(min, getMinCut(s, i + 1, dp) + 1);
            }
        }
        return min;
    }
}