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=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; ib?b:a;
    }
};

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

相关博文：

定制桌面成功案例

海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）

汉字转拼音c/c++源码，支持gb2312和utf8

数据库顶级会议——SIGMOD介绍