[LeetCode] Palindrome Partitioning II

Given a strings, partitionssuch that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning ofs.

For example, givens="aab",Return1since 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)。

若不给自己设限，则人生中就没有限制你发挥的藩篱。