分析
類型 動(dòng)態(tài)規(guī)劃 + 字符串
動(dòng)態(tài)規(guī)劃問(wèn)題的核心在于利用之前的結(jié)果節(jié)省當(dāng)前計(jì)算的開(kāi)銷
本問(wèn)題的解法亮點(diǎn)在于
- 同字符字串的快速移動(dòng)
- 通過(guò)比較當(dāng)前的最長(zhǎng)子串的長(zhǎng)度與剩余未檢查的字符串長(zhǎng)度霞扬，提前結(jié)束計(jì)算
Fastest Code
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
string longestPalindrome(string s)
{
int len = s.size();
int start = 0;
int left,right;
int maxlen = 0;
int maxleft = 0;
while(len - start > maxlen / 2)
{
left = right = start;
while(right < len - 1 && s[right+1]==s[left]) right++;
start = right + 1;
while(left > 0 && right < len - 1 && s[left-1]==s[right+1])
{
left--;
right++;
}
if(right-left+1>maxlen)
{
maxlen = right - left + 1;
maxleft = left;
}
}
return s.substr(maxleft, maxlen);
}
};
