5. 最长回文子串

地址：5. 最长回文子串

状态：阅读题解，书写代码AC

代码：
动态规划：
状态转移方程：

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() <= 1) return s;
        int len = s.size();
        string ans;
        vector<vector<int>> dp(len, vector<int>(len));
        for(int l = 0;l<len;l++){
             for(int i = 0;i+l<len;i++){
                int j = i+l;
                if(l == 0) dp[i][j] = 1;
                else if(l == 1) {
                  dp[i][j] = (s[i] == s[j]);
                }else{
                    dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];
                }
                if(dp[i][j] && (l+1>ans.size())){
                    ans = s.substr(i,l+1);
                }
            }
        }
        return ans;
    }
};

中心扩散：

class Solution {
public:
    string longestPalindrome(string s) {
       if (s == "")return "";
        int len = s.length();
        int index = 0,maxL=0,begin=0;
        while (index < len) {
            int right = index, left = index;
            while (index < len&&s[index + 1] == s[index]) {
                index++;
                right++;
            }
            while (right < len&&left >= 0 && s[right] == s[left]) {
                right++;
                left--;
            }
            right--, left++;
            if (right-left+ 1 > maxL) {
            maxL = right - left + 1;
            begin = left;
            }
            index++;
        }
        return s.substr(begin, maxL);
    }
};