LeetCode:Longest Palindromic Substring

分析

类型 动态规划 + 字符串
动态规划问题的核心在于利用之前的结果节省当前计算的开销

本问题的解法亮点在于

• 同字符字串的快速移动
• 通过比较当前的最长子串的长度与剩余未检查的字符串长度，提前结束计算

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);
    }
};