【LeetCode & 剑指offer刷题】字符串题13：Longest Palindromic Substring

【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）

Longest Palindromic Substring

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"

C++

//问题：最长回文子串
//方法一：O(n^2),O(1)
class Solution
{
private:
    int start,maxlen; //类的成员变量
public:
string longestPalindrome(string s)
    {
        int len = s.size();
        if(len < 2) return s;
       
        start = maxlen = 0;//成员变量初始化（一般在构造函数里通过初始化列表初始化，这里仅为解题方便）
        for(int i = 0; i< len; i++) //扫描字符串，扫描到的字符作为回文的中心字符
        {
            extendPalindrome(s, i, i); //假定奇数长度的子串，从中心扩展回文
            extendPalindrome(s, i, i+1); //假定偶数长度的子串，从中心两个元素扩展回文
        }
      //  cout<<start<<" "<<maxlen<<endl;
        return s.substr(start, maxlen); //注意：substr(pos, count)返回含子串 [pos, pos+count) 的 string
    }
   
private:
    void extendPalindrome(string& s, int left, int right)
    {
        while(left>=0 && right<s.size() && s[left] == s[right])//由中心向两边扩展（问题valid Palindrome中为从两边开始向中间扫描）
        {
            left--;
            right++;
        }//循环结束后，left和right分别指向实际区间左右各偏一个长度的位置
        if(right-left-1 > maxlen) //通过成员变量在成员函数之间传值 
        {
            start = left+1;//更新起始点
            maxlen = right-left-1;//更新最大长度
        }
    }
};
 
//方法二：Manacher's Algorithm  O(n)