问题： 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: “babad”

输出: “bab”

注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”

输出: “bb”

分析过程

https://www.jianshu.com/p/a7741619dd58

方法

  1. class Solution {
  2. public:
  3.     string longestPalindrome(string s) {
  4.         const int n=s.size();
  5.         if(n<=1){
  6.             return s;
  7.         }
  8.         bool f[n][n];
  9.         fill_n(&f[0][0],n*n,false);
  10.         size_t max_len=1;
  11.         size_t start=0;
  12.         for(size_t i=0;i<n;i++){
  13.             f[i][i]=true;
  14.             for(size_t j=0;j<i;j++){
  15.                 f[j][i]=(s[j]==s[i]&&(i-j<2||f[j+1][i-1]));
  16.                 if(f[j][i]&&max_len<(i-j+1)){
  17.                     max_len=i-j+1;
  18.                     start=j;
  19.                 }
  20.             }
  21.         }
  22.         return s.substr(start,max_len);
  23.     }
  24. };