Leetcode: Palindrome Partitioning 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.

难度：90. 这道题跟Palindrome Partitioning非常类似，区别就是不需要返回所有满足条件的结果，而只是返回最小的切割数量就可以。做过Word Break的朋友可能马上就会想到，其实两个问题非常类似，当我们要返回所有结果（Palindrome Partitioning和Word Break II）的时候，使用动态规划会耗费大量的空间来存储中间结果，所以没有明显的优势。而当题目要求是返回某个简单量（比如Word Break是返回能否切割，而这道题是返回最小切割数）时，那么动态规划比起brute force就会有明显的优势。这道题先用Palindrome Partitioning中的方法建立字典，接下来动态规划的方式和Word Break是完全一样的，我们就不再细说了，不熟悉的朋友可以看看Word Break的分析哈。因为保存历史信息只需要常量时间就能完成，进行两层循环，时间复杂度是O(n^2)。空间上需要一个线性数组来保存信息，所以是O(n)。

第二遍做法：比第一遍稍改进一点

关于14行：if dic[0][i-1] 说明0到i-1就是回文，mincut=0

public class Solution {
    boolean[][] dic;
    public int minCut(String s) {
        if (s==null || s.length()==0) return 0;
        dic = new boolean[s.length()][s.length()];
        getDict(s);
        int[] dp = new int[s.length()+1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i=2; i<=s.length(); i++) {
            dp[i] = i-1;
            for (int j=0; j<=i-1; j++) {
                if (dic[j][i-1]) {
                    dp[i] = Math.min(dp[i], j==0? 0 : dp[j]+1);
                }
            }
        }
        return dp[s.length()];
    }
    
    public void getDict(String s) {
        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 || dic[i+1][j-1]))
                    dic[i][j] = true;
            }
        }
    }
}

第一遍过得时候的做法：res[k]的意思是：string前k个元素组成的substring的最小cut数，res[0]=0, res[1]=0, 其它index初始化为res[k] = k-1。因为前k个元素最多需要k-1个cut就能确保每个substring是回文（每个都只有一个字符），然后迭代开始，递归表达式为if dict[0][i-1]为真，res[i]=0; else if dict[j][i-1]为真，res[i] = Math.min(res[i], res[j]+1)

public class Solution {
    public int minCut(String s) {
        if (s==null || s.length()==0 || s.length()==1) return 0;
        boolean[][] dict = getdict(s);
        int[] res = new int[s.length()+1];
        res[0] = 0;
        res[1] = 0;
        for (int k=2; k<=s.length(); k++) {
            res[k] = k-1;
        }
        for (int i=2; i<=s.length(); i++) {
            for (int j=0; j<i; j++) {
                if (j==0 && dict[j][i-1]) res[i] = 0;
                else if (dict[j][i-1]) {
                    res[i] = Math.min(res[i], res[j]+1);
                }
            }
        }
        return res[s.length()];
    }
    
    public boolean[][] getdict(String s) {
        boolean[][] res = new boolean[s.length()][s.length()];
        for (int i=s.length()-1; i>=0; i--) {
            for (int j=i; j<s.length(); j++) {
                if (s.charAt(j)==s.charAt(i) && (j-i<2 || res[i+1][j-1]))
                    res[i][j] = true;
            }
        }
        return res;
    }
}