给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

力扣讲解代码 > https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/

一：动态规划法：

string longestPalindrome(string s) {
    if (s.empty() || s.size() == 1)
        return s;
    vector<vector<bool> > dp(s.size(), vector<bool>(s.size(), false));
    for (int i = 0; i < s.size(); ++i)
    {
        dp[i][i] = true;
    }
    for (int i = 1; i < s.size(); ++i)
    {
        for (int j = 0; j<i; ++j)
        {

            if (s[j] == s[i])
            {
                if (i - j < 3)
                    dp[j][i] = true;
                else
                    dp[j][i] = dp[j + 1][i - 1];
            }
        }
    }

    int index=0,maxLen = 0;
    for (int i = 0; i < s.size(); ++i)
    {
        //这里j与i起点一致，是为了表明单独的一个字母也是有效的回文子串
        for (int j = 0; j <= i; ++j)
        {
            if (dp[j][i] && maxLen < i - j + 1)
            {
                maxLen = i - j + 1;
                index = j;
            }
        }
    }
    return s.substr(index, maxLen);
}

二：中心扩散法

string centerSpread(string s, int left, int right) {
    // left = right 的时候，此时回文中心是一个空隙，向两边扩散得到的回文子串的长度是奇数
    // right = left + 1 的时候，此时回文中心是一个字符，向两边扩散得到的回文子串的长度是偶数
    int size = s.size();
    int i = left;
    int j = right;
    while (i >= 0 && j < size) {
        if (s[i] == s[j]) {
            i--;
            j++;
        }
        else {
            break;
        }
    }
    // 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
    return s.substr(i + 1, j - i - 1);
}

string longestPalindrome(string s) {
    // 特判
    int size = s.size();
    if (size < 2) {
        return s;
    }

    int maxLen = 1;
    string res = s.substr(0, 1);

    // 中心位置枚举到 len - 2 即可
    for (int i = 0; i < size - 1; i++) {
        string oddStr = centerSpread(s, i, i);
        string evenStr = centerSpread(s, i, i + 1);
        string maxLenStr = oddStr.size() > evenStr.size() ? oddStr : evenStr;
        if (maxLenStr.length() > maxLen) {
            maxLen = maxLenStr.size();
            res = maxLenStr;
        }
    }
    return res;
}