最长回文子串

devtools/2025/2/25 11:21:05/

标题

1.1 问题描述

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

1.2 示例

1.2.1 示例1

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

1.2.2 示例2

输入：s = “cbbd”
输出：“bb”

1.3 提示

输入：s = “cbbd”
输出：“bb”

1.4 思路分析

在解决最长回文子串问题时，采用的是中心扩展法。首先，回文串具有对称特性：无论是奇数长度（如“aba”）还是偶数长度（如“abba”），其中心可能是单个字符或相邻的两个字符。因此，可以设计了一个辅助函数center，用于判断当前位置是否是某个回文字符串的中心点，即输入当前中心点的左右边界，通过向两侧扩展判断是否满足回文条件。例如，以索引 i 为中心的单数情况调用center(s,i,i)，而处理双数情况时则调用center(s,i,i+1)。
遍历字符串的每一个位置时，需要同时考虑这两种中心扩展的可能性。每次扩展后，函数返回当前中心能构成的最长回文子串的左右边界。例如，对于字符串“babad”，当 i=1 时，单数扩展得到“bab”（边界0-2），双数扩展无结果，此时记录下当前最长边界。通过比较每次单双数扩展的结果，动态更新全局最长回文的起始和终止索引。最终，通过 substr 截取最长子串。这种方法的时间复杂度为O(n²)，但避免了动态规划的空间开销，且逻辑直观，覆盖了所有可能的回文中心。

1.5 代码

#include<bits/stdc++.h>
using namespace std;
pair<int,int> center(string s,int left,int right){while((left>=0)&&(right<s.size())&&(s[left]==s[right])){left--;right++;}return {left+1,right-1};
}
string longestPalindrome(string s) {int start=0;int end=0;for(int i=0;i<s.size();i++){// 处理以回文长度为单数的情况auto [l1,r1] = center(s,i,i);// 处理回文长度为双数的情况auto [l2,r2] = center(s,i,i+1);if(r1-l1>end-start){start = l1;end = r1;}if(r2-l2>end-start){start = l2;end = r2;}}return s.substr(start,end-start+1);
}int main(){string s = "babad";cout<<longestPalindrome(s)<<endl;
}