題目描述
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",
Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.
解題思路
本題所使用的方法是動(dòng)態(tài)規(guī)劃则果。用一個(gè)數(shù)組马篮，mc[]來(lái)保存從第0個(gè)字符到當(dāng)前字符的最小切割數(shù)威创，比如宠能，mc[j]表示0到j(luò)之間的字符串的最小切割數(shù)。
注意以下幾點(diǎn)：
- 當(dāng)s[i..j]是回文串時(shí)鸭蛙，mc[j]=min(mc[i-1]+1,mc[j])川尖。mc[i-1]+1，很好理解藻糖，就是前一個(gè)回文串的最小切割加上1個(gè)切割淹冰。可為什么要與mc[j]比較取最小值呢巨柒？因?yàn)橛Ｋ琺c[j]中保存著到j(luò)這個(gè)字符的不同切割方法的最小切割數(shù)，也就是無(wú)論怎樣洋满，mc[j]中的值都是表示0到j(luò)之間的字符串的最小切割數(shù)（目前為止的）晶乔，所以要和它比較，如果比它還小牺勾，就把mc[j]值更新成更小的正罢。
- 當(dāng)s[i...j]不是回文串時(shí)，那么mc[j]=min(mc[j-1]+1,mc[j])驻民。mc[j-1]表示到上一個(gè)字符的最小切割翻具，到下一個(gè)字符不是回文袱饭，就把下一個(gè)字符單獨(dú)拿出作為回文，把到上一個(gè)字符最小切割數(shù)加上1呛占，作為到這個(gè)字符的最小切割數(shù)虑乖。mc[j]的解釋和上一點(diǎn)相同。
- 最后一個(gè)mc[s.size()-1]是整個(gè)串的最小切割數(shù)晾虑。
解題代碼
class Solution {
bool isPal(string s,int left,int right){
for(int i=left,j=right;i<j;i++,--j){
//cout<<*i<<" "<<*j<<endl;
if(s[i]!=s[j]) return false;
}
return true;
}
public:
int minCut(string s) {
vector<int> mc(s.size(),0);
for(int i=0;i<s.size();++i){
//mc[i]=mc[i-1]+1;
for(int j=i;j<s.size();++j){
//mc[j]=m[i]+1;
if(i>0){
if(isPal(s,i,j)){
mc[j]=min(mc[j],mc[i-1]+1);
}else{
mc[j]=min(mc[j],mc[j-1]+1);
}
}else{
if(isPal(s,i,j)){
mc[j]=0;
}else{
mc[j]=mc[j-1]+1;
}
}
}
}
return mc[s.size()-1];
}
};
