class Solution {
public:
int minCut(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int a = froml(s);
int b = fromr(s);
return a>b?b:a;
}
int froml(string s){
int length = s.length();
if (1 == length) return 0;
char * pc = new char[length+1];
strcpy(pc,s.c_str());
int len = length-1;
char* pbc = pc;
char* pec = pc+len;
int count = 0;
bool flag = false;
while(1){
int l = (pec - pbc)/2;
int i = 0;
for (;i<=l ;i++){
if(*(pbc+i) != *(pec-i)){
flag = false;
break;
}
flag = true;
}
if(!flag){
pec--;
}else{
if(pec != pc + len){
count++;
pbc = pec + 1;
pec = pc + len;
}else{
break;
}
}
}
return count;
}
int fromr(string s){
int length = s.length();
if (1 == length) return 0;
char * pc = new char[length+1];
strcpy(pc,s.c_str());
int len = length-1;
//reverse
int j = 0;
for (;j<=len/2;j++){
char temp = pc[j];
pc[j] = pc[len-j];
pc[len-j] = temp;
}
char* pbc = pc;
char* pec = pc+len;
int count = 0;
bool flag = false;
while(1){
int l = (pec - pbc)/2;
int i = 0;
for (;i<=l ;i++){
if(*(pbc+i) != *(pec-i)){
flag = false;
break;
}
flag = true;
}
if(!flag){
pec--;
}else{
if(pec != pc + len){
count++;
pbc = pec + 1;
pec = pc + len;
}else{
break;
}
}
}
return count;
}
};