题解---Leetcode.5. 最长回文子串

5. 最长回文子串

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

示例 1：

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

示例 2：

输入：s = "cbbd"
输出："bb"

示例 3：

输入：s = "a"
输出："a"

示例 4：

输入：s = "ac"
输出："a"

提示：

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

Solution

• 扫描，从一个中心点扩张
• 向左向右两个方向扩张
• 当长度为偶数的时候，从边界两侧[i,j] 即i-1 j+1开始扩张
• 长度为奇数，从边界i和j+1开始扩张即可
• 更新区间长度和答案

Language: C++

string longestPalindrome(string s) {
        string res; //临时存储
        int l, r; //左右边界
        for(int i = 0; i < s.size(); i++){
            l = i - 1, r = i + 1; //长度为偶数时候
            while(l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;//扩张区间
            if(r - l - 1 > res.size()) res = s.substr(l + 1, (r - l - 1)); //更新答案
            l = i, r = i + 1; //长度为奇数时候
            while(l >= 0 && r < s.size() && s[l] == s[r]) l--, r++; //扩张区间
            if(r - l - 1 > res.size()) res = s.substr(l + 1, (r - l - 1));//更新答案
        }
        return res;返回答案
    }