【剑斩OFFER】算法的暴力美学——最长回文子串

一、题目描述

二、算法原理

思路：中心扩展算法

我们要遍历字符串，然后固定当前字符串中遍历的字符，例如上图，每次遍历一个字符，那么先让定义两个指针指向当前字符，if : s【 left 】 == s 【 right 】 ，则：left--，right++； if：s[ left ] != s[ right ] ，跟新最长回文字符串：s.substr( left + 1，right - left - 1)，然后不断的重复上面的步骤，就是，都是上图是奇数回文（最长的回文的长度是奇数），当遇到偶数回文时就不行：

最终构造出来的回文字符串：b，不符合题目要求，所以我们要遍历两次，第一次是奇数回文遍历，第二次是偶数回文遍历，总结也就是完成上面的遍历之后，不要急于固定下一个字符，我们要让：left = i，right = i + 1，判断条件跟上面的一样：

此时构造出来的字符串就是我们要的答案：bb

三、代码实现

class Solution { public: string longestPalindrome(string s) { string same;//最长回文 int count = 2;//第一次奇数回文判断，第二次偶数 for(int i = 0; i < s.size(); i++) { int left = i,right = i;//第一次从同一个下标开始 while(count >= 1) { if(left >= 0 && right < s.size() && s[left] == s[right]) { //两边扩散 left--; right++; } else { //奇数或者偶数回文查找结束，更新 same 值 if(same.size() < (right - left -1)) same = s.substr(left + 1,right - left - 1); //偶数回文判断 left = i; right = i + 1; count--; } } count = 2;//为下一次做准备 } return same; } };