132. Palindrome Partitioning II

problem description

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.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

algorithm thought

这里就和前一题重点不同了，这里主要的时间消耗就是判断是否回文的消耗了。

首先我们还是用上一题一样的回文数求法，但是时间太慢了

看了discuss之后明白了很多，求回文数最快的方法还是从中间往两边扩展好些而不是两边向中间扩展。看到这里的朋友可以仔细体会一下两种的区别。

下面给出两种代码

code

//两边向中间扩展
class Solution {
public:
    int minCut(string s) {
        if(s.size()==0)
            return 0;
        vector<int> dp(s.size()+1,0);
        dp[0]=-1;
        for(int i=1;i<s.size();++i){
            dp[i+1]=i;
            for(int j=i;j>=0;--j){
                if(isPalindrome(s,j,i)){
                    dp[i+1]=min(dp[i+1],dp[j]+1);
                }
            }
        }
        return dp.back();
    }
    bool isPalindrome(string&s,int begin,int end){
        while(begin<end){
            if(s[begin++]!=s[end--])
                return false;
        }
        return true;
    }
};

//中间向两边扩展
class Solution {
public:
    int minCut(string s) {
        if(s.size()==0)
            return 0;
        vector<int> dp(s.size()+1,0);
        for(int i=0;i<s.size()+1;++i)
            dp[i]=i-1;

        for(int i=0;i<s.size();++i){

            for(int j=0;(i-j)>=0&&(i+j)<s.size()&&(s[i-j]==s[i+j]);++j){
                dp[i+j+1]=min(dp[i+j+1],dp[i-j]+1);
            }

            for(int j=0;(i-j)>=0&&(i+j+1)<s.size()&&(s[i-j]==s[i+j+1]);++j){
                dp[i+j+2]=min(dp[i+j+2],dp[i-j]+1);
            }

        }
        return dp.back();
    }
};

algorithm analysis

第一个算法最后运行实际是480ms,而第二个算法运行实际是8ms。提升速度可以说是很大了。