LeetCode刷题 题5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

思路：从中心往两边扩散
只有两种情况：
1 abad的情况，从b开始往两边扩散；
2 abbad的情况，从bb开始往两边扩散。

string longestPalindrome(string s) {
        int len = s.size();
        if(len < 2) //若s的长度为0或1，直接返回s
            return s;
        int Maxs = 0, pos = 0;
        for(int i=0; i<len; i++){
            int l1 = zuichang(s, i, i);    //针对是abad的情况，从b开始往两边扩散
            int l2 = zuichang(s, i, i+1);   //针对是abbad的情况，从bb开始往两边扩散
            if(max(max(l1, l2), Maxs) > Maxs){//每次都求回文子串长度的最大值
                Maxs = max(max(l1, l2), Maxs);
                pos = i - (Maxs-1)/2;   //记录每次求得长度最大的回文子串的起始位置
            }  
        }
        string res = s.substr(pos, Maxs);   //从起始位置开始获取该回文子串
        return res;
    }

    int zuichang(string s, int left, int right){   //函数作用：从中心往两边扩散
        while(left>=0 && right<s.size() && s[left] == s[right]){
            left--;
            right++;
        }
        return right-left-1;
    }