Palindrome Partitioning II -- LeetCode

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

public int minCut(String s) {
    if(s == null || s.length()==0)
        return 0;
    boolean[][] dict = getDict(s);
    int[] res = new int[s.length()+1];
    res[0] = 0;
    for(int i=0;i<s.length();i++)
    {
        res[i+1] = i+1;
        for(int j=0;j<=i;j++)
        {
            if(dict[j][i])
            {
                res[i+1] = Math.min(res[i+1],res[j]+1);
            }
        }
    }
    return res[s.length()]-1;
}
private boolean[][] getDict(String s)
{
    boolean[][] dict = 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(i)==s.charAt(j) && (j-i<2 || dict[i+1][j-1]))
                dict[i][j] = true;
        }
    }
    return dict;
}

这个问题和Word Break可以说是一个题目，这里多了一步求解字典。如果求解所有结果时，他们没有多项式时间的解法，复杂度取决于结果数量，而当求解某一种统计的特殊量时，用动态规划就会很大的优势，可以降低时间复杂度。