Leetcode刷题笔记题解（C++）：5. 最长回文子串

思路一：从第一个开始进行扩展

扩展有两种扩展方式：1.以一个字符为中心进行扩展 2.以两个字符为中心进行扩展

代码如下：

class Solution {
public:
    int loc,maxlen; //用于记录起始位置以及回文串的最长长度
    string longestPalindrome1(string s) {
        int length=s.length();
        if(length<2) return s;

        for(int i=0;i<length-1;i++){
            extend(s,i,i); //以一个点作为中点扩展
            extend(s,i,i+1); //以两个点作为中点扩展
        }
        return s.substr(loc,maxlen);
    }

    //向两边扩展
    void extend(string s,int j, int k){
        while(j>=0&&k<s.length()&&s[j]==s[k]){
            j--;k++;
        }
        //如果求得的回文串长度大于之前最大长度，更新回文串第一个位置下标以及最大长度
        if(maxlen<k-j-1){
            loc=j+1;
            maxlen=k-j-1;
        }
    }
};

思路二：动态规划的思路，用二维数组来标记最长的回文串的前端与 后端，具体思路见图

代码如下：

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