題目
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比藻、奇數(shù)長度的回文子串铝量，以當前遍歷元素為中心向兩邊擴散，比如題目給出的第一個例子
- 2韩容、偶數(shù)長度的回文子串款违，以當前遍歷元素和其后一位元素為中心，向兩邊擴散群凶，比如題目給出的第二個例子插爹。
首先想到的是雙重循環(huán)，首先是循環(huán)遍歷字符串的每個字符请梢，然后向兩邊擴散也需要一重循環(huán)赠尾。
js實現(xiàn)
不帶注釋版：
/**
* @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('');//轉成數(shù)組,直接對s進行操作并不會縮短執(zhí)行時間
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;//不是就跳下次循環(huán)
}
else break;//對稱字符一旦不同凡蜻，跳出循環(huán)
}
if(i < arr.length - 1 && arr[i] == arr [i+1]){//回文串長度為偶數(shù)時
if(end - start < 2){//在上面if里已經(jīng)有對稱相同的字符了澜沟，就需要看需不需要改寫start矾兜、end
start = i;
end = i + 1;
}
for(let j = 1; j <= i && i + j +1 < arr.length; j++){//循環(huán)向兩邊擴散檩帐，注意邊界
if(arr[i-j] == arr[i +j +1]){//對稱字符相同
if(2 * j + 2 > end - start +1){//判斷是不是最長
start = i - j;
end = i + j + 1;
}
else continue;//不是就跳下次循環(huán)
}
else break;//對稱字符一旦不同，跳出循環(huán)
}
}
}
return s.substring(start,end + 1);//返回最長回文子串
};
總結
求解最長回文子串思路還是很清晰的元咙，注意一下邊界就行梯影，還有就是js中substring(start, end)函數(shù)是截取的字符串包括index=start的元素，但不包括index=end的元素庶香，所以return時甲棍，end+1了。
