题解 | #编号子回文I#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

字符串处理，回文串判断

题目解答方法的文字分析

题目要求在一群牛的编号中找出最长的回文串。回文串是指正读反读都一样的字符串。

思路：

1. 遍历给定的字符串 s，以每个字符为中心，向两边扩展，查找以当前字符为中心的最长回文串。
2. 由于回文串可能是奇数或偶数长度的，因此需要考虑两种情况：以当前字符为中心的奇数长度回文串和偶数长度回文串。
3. 在扩展过程中记录当前找到的最长回文串，并在遍历完所有字符后返回结果。

举例说明：例如，给定字符串 "babad"，以每个字符为中心，向两边扩展，最长的回文串是 "babad"。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) {
            return "";
        }
        
        int start = 0; // 记录最长回文串的起始位置
        int maxLen = 0; // 记录最长回文串的长度
        
        for (int i = 0; i < s.length(); ++i) {
            // 以当前字符为中心的奇数长度回文串
            int len1 = expandAroundCenter(s, i, i);
            // 以当前字符和下一个字符为中心的偶数长度回文串
            int len2 = expandAroundCenter(s, i, i + 1);
            
            int len = max(len1, len2);
            // 如果当前找到的回文串更长，则更新记录
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }
        
        return s.substr(start, maxLen);
    }
    
private:
    // 扩展以 left 和 right 为中心的回文串，并返回回文串的长度
    int expandAroundCenter(string& s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        // 注意：因为跳出循环时左右指针已经多移动了一位，所以计算长度要减 1
        return right - left - 1;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！