雖然寫得爛而且TLE,好歹是正确的。。還是值得紀念的
class Solution {
public:
int pcut(string s, int start, int end){
if (start >= end)return 0;
stack<tuple<int, int>> pre;
tuple<int, int> tmp;
int i = 0, i2, j;
int fir, sec, overlap;
for (i = start; i < end; i++)
{
i2 = i;
while (i2 + 1 < end && s[i2] == s[i2 + 1]) i2++;
j = 0;
while (i - j - 1 >= start && i2 + j + 1 < end && s[i - j - 1] == s[i2 + j + 1]) j++;
if (!pre.empty()){
tmp = pre.top();
//如果被包含在上一個回文中,則直接跳過
if (i2 + j <= get<1>(tmp))
{
i = i2; continue;
}
//找出包含在目前回文中的以前的回文并删除
while (get<0>(tmp) >= i - j)
{
pre.pop();
if (pre.empty())
{
break;
}
tmp = pre.top();
}
if (!pre.empty())
{
fir = get<0>(tmp), sec = get<1>(tmp);
//處理重疊的部分
if (fir < i - j && sec >= i - j)
{
int min1 = pcut(s, start, i - j) + pcut(s, i - j, end);//收縮上一個回文
int min2 = pcut(s, start, sec + 1) + pcut(s, sec + 1, end);//收縮目前回文
return min1 < min2 ? min1 + 1 : min2 + 1;
}
}
}
pre.push(make_tuple(i - j, i2 + j));
i = i2;
}
return pre.size() - 1;
}
int minCut(string s) {
if (s.length() <= 1)return 0;
return pcut(s, 0, s.length());
}
};
雖然寫得爛而且TLE,好歹是正确的。。還是值得紀念的