【LeetCode5】最大回文子串（中心扩散法）

【LeetCode5】最大回文子串（中心扩散法） 一、题目

提示：

1 <= s.length <= 1000s 仅由数字和英文字母（大写和/或小写）组成 二、思路

中心扩散法。

从每个节点开始，当前结点向两边扩散来判断回文串，因为回文串长度可能是奇数或者偶数，即后者就木有一个中心字符，伪代码应该如下：

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和 s[i+1] 为中心的回文串
    更新答案

我们通过传入的左指针l和右指针r，可以同时处理回文串为奇数和偶数的情况。注意palindrome函数最后的s.substr(l+1, r-1-l)中，右边界是相对下标，其计算是：(r-1)-(l+1)+1=r-l-1。

三、代码

class Solution {
public:
    string longestPalindrome(string s) {
        string ans;
        for(int i = 0; i < s.size(); i++){
            //以s[i]为中心的最长回文子串
            string s1 = palindrome(s, i, i);
            //以s[i]和s[i+1]为中心的最长回文子串
            string s2 = palindrome(s, i, i + 1);
            //ans = longest(ans, s1, s2)
            if(ans.size() < s1.size()){
                ans = s1;
            }
            if(ans.size() < s2.size()){
                ans = s2;
            }
        }
        return ans;
    }
    string palindrome(string& s, int l, int r){
        //防止索引越界
        while(l >= 0 && r < s.size() && s[l] == s[r]){
            //向两边展开
            l--;r++;
        }
        return s.substr(l + 1, r - l - 1);
    }
};