/*给定一个字符串 s，找到 s 中最长的回文子串。你可以假设?s 的最大长度为 1000。
示例 1：
输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2：
输入: “cbbd” 输出: “bb”
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-substring 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
class Solution { public: int start = 0; int maxlen = 0; void is_legal(string s, int left, int right) { if (s.empty()) return; while (left >= 0 && right < s.size() && s[left] == s[right]) { //中心扩散法，以每一个字符为中心向两边扩散，判断是否回文， //是，并记录，开始位置，最大长度，之后继续扩散 left--; right++; } if (maxlen < (right - left - 1)) { maxlen = right - left - 1; start = left + 1; } } string longestPalindrome(string s) { if (s.empty()) return s; //中心扩散法，以每一个字符为中心向两边扩散，判断是否回文， //是，并记录，开始位置，最大长度，之后继续扩散 for (int i = 0; i < s.size(); ++i) { //奇数个字符 is_legal(s, i, i); //偶数个字符 is_legal(s, i, i + 1); } return s.substr(start, maxlen); } };