题目

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

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

思路

通过动态规划来解，设字符串为str，设二维数组dpi，表示str[i]到str[j]的子串是否为回文字串，并用pre，last作为标记，保存已找到的最长的回文字串。并且，只要当dpi-1为true，那么只要str[i]==str[j]即可，特殊情况有i=j+1，需要考虑。

代码

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.length()==0) {
            return "";
        }
        int n = s.length();
        bool dp[n][n];
        int pre = 0, last = 0;
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            for (int j = i-1; j >= 0; j--) {
                dp[i][j] = (s[i] == s[j]) && (i-j==1 || dp[i-1][j+1]);
                if (dp[i][j] && (i-j)>(last-pre)) {
                    last = i;
                    pre = j;
                }
            }
        }
        return s.substr(pre, last-pre+1);
    }
};