康瑞部落

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.

解题思路：

动态规划。用d[i]表示前i个字符需要的最大切分数目。则d[i+1]的最大值不会超过d[i]+1。若第i+1个字符与前面第j个字符开始构成回文，则d[i+1]=min(d[i]+1, d[j-1]+1)。注意这里要验证每个j的情况。下面是相关代码：

class Solution {
public:
    int minCut(string s) {
        int len=s.length();
        if(len==0||len==1){
            return 0;
        }
        int* d=new int[len];
        d[0]=0;
        for(int i=1; i<len; i++){
            d[i]=d[i-1]+1;
            for(int j=0; j<i; j++){
                int l=j, r=i;
                while(l<r){            //验证j到r是否为回文
                    if(s[l]==s[r]){
                        l++;
                        r--;
                    }else{
                        break;
                    }
                }
                if(l>=r){           //表示j到i是回文
                    if(j==0){
                        d[i]=0;
                    }else{
                        d[i]=min(d[i], d[j-1]+1);
                    }
                }
            }
        }
        
        int result=d[len-1];
        delete[] d;
        return result;
    }
    
    int min(int a, int b){
        return a>b?b:a;
    }
};

提交上去，发生超时错误。这个算法的时间复杂度为O(n3)。能否更快呢？原来在检查j到i是否为回文的过程中，我们做了很多重复运算。假如我们知道s[j+1, i-1]是回文，若s[j]==s[i]，那么s[j, i]也是回文。因此我们可以用一个二维数组来记录这个特征。下面是改后的代码。

class Solution {
public:
    int minCut(string s) {
        int len=s.length();
        if(len==0||len==1){
            return 0;
        }
        
        bool** bIsPalin=new bool*[len];     //二维数组，表示i到j是否是回文
        for(int i=0; i<len; i++){
            bIsPalin[i] = new bool[len];
            bIsPalin[i][i] = true;          //自身到自身是回文
        }
        
        for(int i=0; i<len; i++){
            for(int j=0; j<i; j++){
                if(i==j+1){
                    if(s[i]==s[j]){
                        bIsPalin[j][i]=true;
                    }else{
                        bIsPalin[j][i]=false;
                    }
                }else{
                    bIsPalin[j][i]=s[i]==s[j]&&bIsPalin[j+1][i-1];
                }
            }
        }
        
        int* d=new int[len];
        d[0]=0;
        
        for(int i=1; i<len; i++){
            d[i]=d[i-1]+1;          //上限值
            for(int j=0; j<i; j++){
                if(bIsPalin[j][i]){
                    if(j==0){
                        d[i]=0;
                    }else{
                        d[i]=min(d[i], d[j-1]+1);
                    }
                    //break;
                }
            }
        }
        
        int result=d[len-1];
        //释放空间
        delete[] d;
        for(int i=0; i<len; i++){
            delete[] bIsPalin[i];
        }
        delete[] bIsPalin;
        
        return result;
    }
    
    int min(int a, int b){
        return a>b?b:a;
    }
};

更改后的代码的时间复杂度为O(n2)。