dedecms 网站访问量2022近期重大新闻事件10条

5. 最长回文子串

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

。思路：

对于第i个字符，可能的回文子串构成方式有两种，一种是以i位置元素为中心元素，向着两边扩展，一种是以i位置和i+1位置元素为中心，分别向两边扩展。因此对于每个字符i，按照上述两种方式分别求出以当前位置为中心的最长回文字串，然后判断最长是哪个即可。

class Solution {
public:string longestPalindrome(string s) {int n = s.size();if (n == 1)return s;int ret = 0;string ssret;for (int i = 0; i < n; i++){int j = 1;int len1 = 1;while (i - j >= 0 && i + j < n && s[i - j] == s[i + j]){len1 += 2;j++;}j = 0;int len2 = 0;while (i - j >= 0 && i + 1 + j < n && s[i - j] == s[i + j+1]){len2+=2;j++;}if (len1 > len2){if (ret < len1){ssret = s.substr(i - len1 / 2, len1);ret = len1;}}else{if (ret < len2){ssret = s.substr(i + 1 - len2 / 2, len2);ret = len2;}}}return ssret;}
};