问题描述
给定一个字符串
s，找到s中最长的回文子串。你可以假设s的最大长度为 1000。
示例
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
代码：
class Solution {
public:string longestPalindrome(string s) {int maxl = 0;int left = 0, right = 0;s.insert(0, "$");//防止最左出界for(int i = 1; s[i]; i++){int tl = i, tr = i;int len = 0;while(s[tr+1] == s[tl])tr++;while(s[tl-1] == s[tr+1]){tl--;tr++;}len = tr - tl +1;if(len > maxl){maxl = len;left = tl;right = tr;}}if(!left && !right)//应对空字符串特殊情况return s.substr(1,1);return s.substr(left, maxl);}
};
思路：
以每个字符为中心，先向右探索与该字符相同的字符，然后左右同时探索，相同则移动，保存最长回文子串的起始位置。
有两个细节需要注意：
一是当字符串不空对第一个字符进行探索时，当走到左右同时探索这一步时会出界，所以在头部插入一个字符
二是当字符串为空时，for循环无效，需要单独处理。