知识点
字符串
思路
暴力,对于每个点s[i],依次向左右延伸,寻找以该点为中心的奇数长度回文字符串(长度至少为1),以及以该点与其右边点为中心的偶数长度回文字符串(长度至少为0)。每次向左右延伸,字符串长度增加2。每次在到达边界或者不构成回文时,使用现在字符串的长度与已储存的最长长度作比较,若当前的更大,则更新,并且更新这个字符串的左端点坐标,最后根据左端点坐标与字符串长度求出答案并返回即可。
代码c++
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param s string字符串
* @return string字符串
*/
string longestPalindrome(string s) {
int len = 0;
int ans = 0;
for (int i = 0; i < s.size(); i++) {
// cout << s[i] << endl;
for (int l = i - 1, r = i + 1, t = 0; l >= 0 &&
r <= s.size() - 1; l--, r++, t++) {
// cout << l << " " << r << endl;
// cout << s[l] << " " << s[r] << endl;
if (s[l] != s[r]) {
if (len < (2 * t) + 1) {
ans = l + 1;
len = 2 * t + 1;
}
break;
}
if (l == 0 || r == s.size() - 1) {
if (len < (2 * t) + 3) {
ans = l;
len = 2 * t + 3;
}
break;
}
}
// cout << 1 << " " << ans << " " << len << endl;
for (int l = i, r = i + 1, t = 0; l >= 0 && r <= s.size() - 1; l--, r++, t++) {
if (s[l] != s[r]) {
if (len < 2 * t) {
ans = l + 1;
len = 2 * t;
}
break;
}
if (l == 0 || r == s.size() - 1) {
if (len < (2 * t) + 2) {
ans = l;
len = 2 * t + 2;
}
break;
}
}
// cout << 2 << " " << ans << " " << len << endl;
}
string anss;
for (int i = ans; i <= ans + len - 1; i++) {
anss += s[i];
}
return anss;
}
};