首页 > 代码库 > Palindrome Partitioning II

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.

 

题解

 这道题需要用动态规划做,如果用I的DFS的方法做会TLE。

 

 首先设置dp变量 cuts[len+1]。cuts[i]表示从第i位置到第len位置(包含,即[i, len])的切割数(第len位置为空)。

 初始时,是len-i。比如给的例子aab,cuts[0]=3,就是最坏情况每一个字符都得切割:a|a|b|‘ ‘。cuts[1] = 2, 即从i=1位置开始,a|b|‘ ‘。

 cuts[2] = 1 b|‘ ‘。cuts[3]=0,即第len位置,为空字符,不需要切割。

 

 上面的这个cuts数组是用来帮助算最小cuts的。

 

 还需要一个dp二维数组matrixs[i][j]表示字符串[i,j]从第i个位置(包含)到第j个位置(包含) 是否是回文。

 如何判断字符串[i,j]是不是回文?

 1. matrixs[i+1][j-1]是回文且 s.charAt(i) == s.charAt(j)。

 2. i==j(i,j是用一个字符)

 3. j=i+1(i,j相邻)且s.charAt(i) == s.charAt(j)

 

 当字符串[i,j]是回文后,说明从第i个位置到字符串第len位置的最小cut数可以被更新了,

 那么就是从j+1位置开始到第len位置的最小cut数加上[i,j]|[j+1,len - 1]中间的这一cut。

 即,Math.min(cuts[i], cuts[j+1]+1) 

 最后返回cuts[0]-1。把多余加的那个对于第len位置的切割去掉,即为最终结果。

 

C++实现代码:

#include<iostream>#include<string>#include<cstring>using namespace std;class Solution {public:    int minCut(string s)    {        if(s.empty())            return 0;        int n=s.length();        bool matrix[n][n];        int cut[n+1];        memset(matrix,false,sizeof(matrix));        memset(cut,0,sizeof(cut));        int i,j;        for(i=0;i<n;i++)            cut[i]=n-i;        for(i=n-1;i>=0;i--)        {            for(j=i;j<n;j++)            {                if((s[i]==s[j]&&j-i<2)||(s[i]==s[j]&&matrix[i+1][j-1]))                {                    matrix[i][j]=true;                    cut[i]=min(cut[i],cut[j+1]+1);                }            }        }        return cut[0]-1;    }};int main(){    Solution s;    int result=s.minCut(string("ababababababababababababcbabababababababababababa"));    cout<<result<<endl;}

使用回溯的方法对大集合会超时:

#include<iostream>#include<vector>#include<string>#include<climits>using namespace std;class Solution{public:    int minCut(string s)    {        if(s.empty())            return 0;        vector<string> path;        int min=INT_MAX;        helper(s,0,path,min);        return min;    }    void helper(string s,int start,vector<string> &path,int &min)    {        int n=path.size();        int i;        int sum=0;        for(int j=0; j<n; j++)        {            sum+=path[j].size();        }        if(sum==(int)s.size())        {            if((int)path.size()-1<min)                min=path.size()-1;            return;        }        for(i=1; i<=(int)s.size()&&start+i<=(int)s.size(); i++)        {            string tmp=s.substr(start,i);            if(!isPalindrome(tmp))                continue;            path.push_back(tmp);            helper(s,start+i,path,min);            path.pop_back();        }    }    bool isPalindrome(string s)    {        if(s.empty())            return true;        int i=0;        int j=s.length()-1;        while(i<=j)        {            if(s[i]!=s[j])                return false;            i++;            j--;        }        if(i>j)            return true;        return false;    }};int main(){    Solution s;    int result=s.minCut(string("abababababab"));    cout<<result<<endl;}

 

Palindrome Partitioning II