题目
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
example
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"
分析
这是leetcode上的第5题，难度为Medium，是要找出给定字符串的最长回文子串，很容易想到有两种情况：
- 1、奇数长度的回文子串，以当前遍历元素为中心向两边扩散，比如题目给出的第一个例子
- 2、偶数长度的回文子串，以当前遍历元素和其后一位元素为中心，向两边扩散，比如题目给出的第二个例子。
首先想到的是双重循环，首先是循环遍历字符串的每个字符，然后向两边扩散也需要一重循环。
js实现
不带注释版：
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
var arr = s.split('');
var start = 0, end = 0;
for(let i = 0; i< arr.length; i++){
for(let j = 1; j <= i && i + j < arr.length; j++){
if(arr[i-j] == arr[i+j]){
if( 2 * j > end - start){
start = i - j;
end = i + j;
}
else continue;
}
else break;
}
if(i < arr.length - 1 && arr[i] == arr [i+1]){
if(end - start < 2){
start = i;
end = i + 1;
}
for(let j = 1; j <= i && i + j +1 < arr.length; j++){
if(arr[i-j] == arr[i +j +1]){
if(2 * j + 2 > end - start +1){
start = i - j;
end = i + j + 1;
}
else continue;
}
else break;
}
}
}
return s.substring(start,end + 1);
};
带注释版：
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
var arr = s.split('');//转成数组,直接对s进行操作并不会缩短执行时间
var start = 0, end = 0;//记录回文串起始
for(let i = 0; i< arr.length; i++){//遍历s
for(let j = 1; j <= i && i + j < arr.length; j++){//注意边界，i-j不超出左边界，i+j不超出右边界
if(arr[i-j] == arr[i+j]){//对称字符相等
if( 2 * j > end - start){//判断是不是最长
start = i - j;
end = i + j;
}
else continue;//不是就跳下次循环
}
else break;//对称字符一旦不同，跳出循环
}
if(i < arr.length - 1 && arr[i] == arr [i+1]){//回文串长度为偶数时
if(end - start < 2){//在上面if里已经有对称相同的字符了，就需要看需不需要改写start、end
start = i;
end = i + 1;
}
for(let j = 1; j <= i && i + j +1 < arr.length; j++){//循环向两边扩散，注意边界
if(arr[i-j] == arr[i +j +1]){//对称字符相同
if(2 * j + 2 > end - start +1){//判断是不是最长
start = i - j;
end = i + j + 1;
}
else continue;//不是就跳下次循环
}
else break;//对称字符一旦不同，跳出循环
}
}
}
return s.substring(start,end + 1);//返回最长回文子串
};
总结
求解最长回文子串思路还是很清晰的，注意一下边界就行，还有就是js中substring(start, end)函数是截取的字符串包括index=start的元素，但不包括index=end的元素，所以return时，end+1了。
