问题
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
分析
递推：s[i][j] = s[i-1][j-1] && s[i] == s[j]，所以要枚举左边界以及右边界，从c++实现来看，枚举子串长度以及左边界，可以计算右边界，写代码比较方便。
代码
class Solution {
public:static const int N = 1e3+10;bool f[N][N]; // f[i][j]表示s[i...j]是否为回文int begin = 0, max_L = 1;int n = 0;string longestPalindrome(string s) {n = s.size();if (n < 2) {return s;}for (int i = 0; i < n; i++) {f[i][i] = true;}// 枚举子串长度for (int L = 2; L <= n; L++) {for (int i = 0; i < n; i++) { // 枚举左边界iint j = L + i - 1;if (j >= n) {break;}if (s[i] != s[j]) {f[i][j] = 0; } else {if (j - i < 3) {f[i][j] = 1; }else {f[i][j] = f[i+1][j-1]; }}if (f[i][j] && j-i+1 > max_L) {max_L = j-i+1;begin = i;}}}return s.substr(begin, max_L);}
};