Question :
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.
Anwser 1 :
class Solution {
public:
int minCut(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (s.size() < 2)
return 0;
int length = s.size();
int *minSegs = new int[length+1];
minSegs[0] = 0;
minSegs[1] = 1;
int **dp = new int*[2];
dp[0] = new int[length+2];
dp[1] = new int[length+2];
dp[0][0] = dp[1][0] = 0;
dp[0][1] = dp[1][1] = 1;
dp[0][2] = -1;
int cur = 0;
int pre = 1;
for (int i=1; i<s.size(); i++) {
int cur = i % 2;
int pre = (i +1) % 2;
minSegs[i+1] = minSegs[i] + 1;
int n = 1;
for (int j=0; dp[pre][j] != -1; j++) {
int left = i-1-dp[pre][j];
if (left>=0 && s[left]==s[i]) {
dp[cur][++n] = dp[pre][j] + 2;
if (minSegs[left] + 1 < minSegs[i+1])
minSegs[i+1] = minSegs[left] + 1;
}
}
dp[cur][++n] = -1;
}
int min = minSegs[s.size()] - 1;
delete []minSegs;
return min;
}
};
Anwser 2: :
class Solution {
public:
int minCut(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len=s.length();
int BIG=2*len;
int num_line=len+1;
vector<int> isPalindrome(num_line*num_line);
for(int l=1;l<=len;l++)//两个木板之间有多少个字符
{
for (int i=0;i+l<num_line;i++)//从第0个木板开始,i+l为木板的序号
{
if (l==1)
{
isPalindrome[i*num_line+(i+l)]=1;
}
else if(l==2)
{
if (s[i]==s[i+l-1])
isPalindrome[i*num_line+(i+l)]=1;
else
isPalindrome[i*num_line+(i+l)]=BIG;
}
else
{
if (s[i]==s[i+l-1])
isPalindrome[i*num_line+(i+l)]=isPalindrome[(i+1)*num_line+(i+l-1)];
else
isPalindrome[i*num_line+(i+l)]=BIG;
}
}
}
vector<int> dist(num_line);
vector<bool> labeled(num_line);
for(int i=0;i<num_line;i++)
{
dist[i]=BIG;
labeled[i]=false;
}
dist[0]=0;
labeled[0]=true;
int current_line=0;
for(int i=1;i<num_line;i++)
{
for(int d=current_line+1;d<num_line;d++)//对所有的相邻(在图中)的木板
{
if(!labeled[d])
{
if (dist[current_line]+isPalindrome[current_line*num_line+d]<dist[d])
{
dist[d]=dist[current_line]+isPalindrome[current_line*num_line+d];
}
}
}
int mindist=BIG;
int minindex=-1;
for(int i=0;i<num_line;i++)
{
if(!labeled[i])
{
if(mindist>dist[i])
{
minindex=i;
mindist=dist[i];
}
}
}
current_line=minindex;
labeled[minindex]=true;
}
return dist[num_line-1]-1;
}
};
参考推荐: