最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

class Solution {
public:
   string longestPalindrome(string s) {
       if(s.size()==1)
           return s;

       // 初始化dp为1
       vector<vector<int>> res(s.size(),vector<int>(s.size(),1));

       // 长度为1的最长回文子串一定为1
       // 长度为2的最长回文子串
       for(int i=0;i<s.size()-1;i++){
           int j=i+1;
           if(s[i]==s[j])
               res[i][j]=2;
       }

       // 长度为3及以上的最长回文子串
       for(int len=3;len<=s.size();len++){
           // i表示回文串的左侧
           for(int i=0;i<=s.size()-len;i++){
               // j表回文串的右侧，通过i和len计算得到右侧
               int j=len+i-1;

               if(s[i]==s[j])
                   res[i][j]=res[i+1][j-1]+2;
               else
                   res[i][j]=max(res[i+1][j],res[i][j-1]);
           }
       }

       // 搜索数组最大的数据，并记录i,j
       int col=0;
       int max_val=0;
       for(int i=0;i<s.size();i++){
           for(int j=i;j<s.size();j++){
               if(res[i][j]>max_val && j-i+1==res[i][j] ){
                   max_val=res[i][j];
                   col=i;
               }
           }
       }
       return s.substr(col,max_val);
   }
};