分析
类型 动态规划 + 字符串
动态规划问题的核心在于利用之前的结果节省当前计算的开销
本问题的解法亮点在于
- 同字符字串的快速移动
- 通过比较当前的最长子串的长度与剩余未检查的字符串长度，提前结束计算
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);
}
};
