当前位置：首页 > article >正文

【C/C++】最长回文子串（leetcode T5）

article 2025/3/17 9:59:40

核心考点：回文+字符串匹配+中心扩展法

题目描述

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

示例 1：

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

示例 2：

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

题目解析：

class Solution {
public:
    // 辅助函数：从中心向两侧扩展，寻找回文串
    string palindrome(string s, int l, int r) {
        // 在字符串范围内扩展，左右字符相等时继续扩展
        while (l >= 0 && r < s.length() && s[l] == s[r]) {
            l--; // 左指针左移
            r++; // 右指针右移
        }
        string res;
        // 截取当前找到的回文串
        for (int i = l + 1; i <= r - 1; i++) {
            res += s[i];
        }
        return res;
    }

    // 主函数：寻找最长回文子串
    string longestPalindrome(string s) {
        string res = ""; // 用于存储最长回文子串
        for (int i = 0; i < s.length(); i++) {
            // 以单个字符为中心，寻找奇数长度回文串
            string s1 = palindrome(s, i, i);
            // 以两个字符为中心，寻找偶数长度回文串
            string s2 = palindrome(s, i, i + 1);
            // 选择长度更长的回文串更新结果
            res = s1.length() > res.length() ? s1 : res;
            res = s2.length() > res.length() ? s2 : res;
        }
        return res;
    }
};

思路分析

这道题的目标是寻找字符串 s 中的最长回文子串。回文字符串即正读和反读都相同的字符串。

解题思路：中心扩展法

中心扩展思想：
- 回文串的特点是中心对称，因此可以从每个字符或两个字符之间的间隙作为中心，向两侧扩展，检查是否为回文。
- 若左右字符相等，继续向外扩展，直到不满足回文条件为止。
分为两种情况进行扩展：
- 单字符中心（奇数长度回文串）：从一个字符作为中心扩展。
- 双字符中心（偶数长度回文串）：从相邻的两个字符作为中心扩展。
记录最长回文串：
- 每次扩展结束后，若得到的回文串长度超过当前最大长度，则更新结果。