1. 题目(中等)
给你一个字符串s
,找到s
中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:
输入:s = “cbbd”
输出:“bb”
提示:
- 1 <= s.length <= 1000
-
s
仅由数字和英文字母组成
2. 分析与题解
首先从回文字符串的定义可以知道,沿着中心轴翻转,则翻转前后的字符串是相同的,如:
换言之,对于中心轴两边的值是相等的,考察的知识点是中心扩散法,沿着中心轴向两端扩散,这也是回文串的主要判断方法,即头尾两个指针向两端移动,并判断两个指针处的值是否相等。
class Solution {
public:
vector<int> cal(string s, int i, int j) {
int n = s.length();
while (i >= 0 && j < n && s[i] == s[j]) {
i --;
j ++;
}
return {i+1, j-1};
}
string longestPalindrome(string s) {
int n = s.length();
int left = 0, right = 0;
int max_len = 0;
for (int i = 0; i < n; i++) {
vector<int> a = cal(s, i, i);
vector<int> b = cal(s, i, i+1);
if (a[1]-a[0]+1 > max_len) {
left = a[0];
right = a[1];
max_len = a[1]-a[0]+1;
}
if (b[1]-b[0]+1 > max_len) {
left = b[0];
right = b[1];
max_len = b[1]-b[0]+1;
}
}
return s.substr(left,right-left+1);
}
};