描述：
給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
示例 1：
輸入: “babad”
輸出: “bab”
注意: “aba” 也是一個有效答案。
示例 2：
輸入: “cbbd”
輸出: “bb”
暴力破解
外面的兩層循環找到所有子串，第三層循環判斷子串是否是回文。方法的時間複雜度為O(n^3)，空間複雜度為O(1)。
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let result = '';
for(let i = 0;i<s.length;i++){
for(let j=i+1;j<=s.length;j++){
let str = s.slice(i,j);
let f = str.split('').reverse().join('');
if(str == f){
result = str.length > result.length ? str : result;
}
}
}
return result;
};
中心擴充法
step 1:周遊每個字元,把每個字元當做中心逐漸向兩邊擴充,每擴充一步就得到一個新的子串。這裡針對輸入字元串的長度，擴充方式需要根據長度奇偶性質做判斷；
Step 2:判斷子串是否為回文串，更新目前最長回文串；
Step 3:傳回最長回文串。
時間複雜度：
周遊字元串的時間複雜度為O(n),中心擴充及判斷子串是否為回文串的時間複雜度為O(n),二者相乘得到動态規劃法的時間複雜度為O(n^2)。
空間複雜度:
該方法沒有使用額外的空間，空間複雜度為O(n)。
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
let maxLen = 0;
let start = 0;
//長度為奇數
for (let i = 0; i < s.length; i++) {
let j = i - 1;
let k = i + 1;
while (j >= 0 && k < s.length && s.charAt(j) === s.charAt(k)) {
if (k - j + 1 > maxLen) {
maxLen = k - j + 1;
start = j;
}
j -= 1;
k += 1;
}
}
//長度為偶數
for (let i = 0; i < s.length; i++) {
let j = i;
let k = i + 1;
while (j >= 0 && k < s.length && s.charAt(j) === s.charAt(k)) {
if (k - j + 1 > maxLen) {
maxLen = k - j + 1;
start = j;
}
j -= 1;
k += 1;
}
}
if (maxLen > 0) {
return s.slice(start, start + maxLen);
} else{
return s.slice(0,1);
}
};
Manacher算法
作用：線性時間解決最長回文子串問題。
思想：Manacher充分利用了回文的性質，進而達到線性時間。
首先先加一個小優化，就是在每兩個字元（包括頭尾）之間加沒出現的字元（如#），這樣所有字元串長度就都是奇數了，友善了很多。
記錄p[i]表示i能向兩邊推（包括i）的最大距離，如果能求出p，則答案就是max§-1了（以i為中點的最長回文為2*p[i]-1，但這是加過字元後的答案，把加進去的字元幹掉，最長回文就是p[i]-1）。
我們假設p[1~i-1]已經求好了，現在要求p[i]：
假設目前能達到的最右邊為R，對應的中點為pos，j是i的對稱點。
1.當i＜R時
由于L~R是回文，是以p[i]=p[j]（i的最長回文和j的最長回文相同）。
這種情況是另一種：j的最長回文跳出L了。那麼i的最長回文就不一定是j的最長回文了，但藍色的肯定還是滿足的。
綜上所述，p[i]=min(p[2*pos-i],R-i)。
2.當i>=R時
由于後面是未知的，于是隻能暴力處理了。
效率：但是這樣看起來很暴力，為什麼複雜度是O(len)的呢？因為R不會減小，每次暴力處理的時候，p[i]增大多少，就說明R增大多少，而R最多增加len次。是以複雜度是O(len)的。
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
if (s.length == 1) {
return s
}
let str = '#' + s.split('').join('#') + '#'
let rl = []
let mx = 0
let pos = 0
let ml = 0
for (let i = 0; i < str.length; i++){
if (i < mx) {
rl[i] = Math.min(rl[2 * pos - i], mx - i)
} else {
rl[i] = 1
}
while (i - rl[i] > 0 && i + rl[i] < str.length && str[i - rl[i]] == str[i + rl[i]]) {
rl[i]++
}
if (rl[i] + i - 1 > mx) {
mx = rl[i] + i - 1
pos = i
}
if (ml < rl[i]) {
ml = rl[i]
sub = str.substring(i - rl[i]+1, i + rl[i])
}
}
return sub.split('#').join('').trim()
};
參考連結：https://blog.csdn.net/zzkksunboy/article/details/72600679 CSDN部落客「ZigZagK」的原創文章，遵循 CC 4.0 BY-SA 版權協定