（力扣）5. 最长回文子串 C++（中心扩散法）解题击败100%用户

5. 最长回文子串

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

解题思路：

中心扩散法

我们是以每一个字符为中心，往两边扩散，来求最长的回文子串。

我们来思考这样一个问题，如果是单个字符，我们可以认为他是回文子串，如果是多个字符，并且他们都是相同的，那么他们也是回文串。所以对于上面的问题，我们以当前字符为中心往两边扩散的时候，先要判断和他挨着的有没有相同的字符，如果有，则跳过继续判断下一个，
根据这个思路，我们来写下代码：

class Solution {
public:
    string longestPalindrome(string s) {
        // 获取字符串s的长度
        int length = s.size(); 
        // 设置回文子串起始位置和字串长度的初始值
        int start = 0, maxlen = 0;
        for(int i = 0; i < length; ){
            // 判断剩余字串长度小于当前回文字串的长度，则直接跳出循环
            if(length - i < maxlen / 2){
                break;
            }
            int left = i, right = i;
            // 过滤掉重复的字符
            while(right < length - 1 && s[right + 1] == s[right]){
                ++right;
            }
            // 下次循环是直接从重复的下一个位置开始判断
            i = right + 1;
            // 往两边开始扩散，求回文字串长度
            while(right < length -1 && left > 0 && s[left - 1] == s[right + 1]){
                --left;
                ++right;
            }
            // 求出最长回文字串长度和起始位置
            if(right - left + 1 > maxlen){
                start = left;
                maxlen = right - left + 1;
            }
        }
        // 返回最长回文字串
        return s.substr(start, maxlen);
    }
};

赏

谢谢你请我喝咖啡

支付宝

微信