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

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

题目描述

给你一个字符串 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 中的最长回文子串。回文字符串即正读和反读都相同的字符串。

解题思路：中心扩展法

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