Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.Example 2:
Input: "cbbd" Output: "bb"解题思路
题目中的回文序列有两种 奇数 和 偶数的两种情况 ~
奇数长度的 回文串 ： ababa, 偶数长度回文串 ： cabbac
对应两种情况遍历第一个到第n - 1个字符串 判断找到起始的字符串的起始位置和最大长度 ~
解题代码：
class Solution { public: void helper (const string &s, int &beg, int &len, int l, int r){ while(l >= 0 && r < s.size() && s[l--] == s[r++]) if(r - l - 1 > len) { len = r - l - 1; beg = l + 1; } } string longestPalindrome(string s) { int l = 0, r = 0, len = 1, beg = 0; for (int i = 1; i < s.size(); i++){ l = i - 1, r = i + 1; if (s[l] == s[i] || s[l] == s[r]){ helper(s, beg, len, l, i); helper(s, beg, len, l, r); } } return s.substr(beg, len); } };