Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.Example 2:
Input: "cbbd"
Output: "bb"Explaining:
最直觀的方法就是從最長的開始往下算，
假設 s = "babad"，就從長度是 5, 4, 3 … 找到長度是 3 有回文 bab
找到後就 return 但是這個作法複雜度是 會超時。
實做在下方
var longestPalindrome = function(s) {
for (let len = s.length; len > 0; len -= 1) {
for (let start = 0; start < s.length - len + 1; start += 1) {
const substr = s.substr(start, len);
if (isPalindrome(substr)) return substr;
}
}
return '';
};
const isPalindrome = (s) => {
const halfLen = Math.floor(s.length / 2);
return s
.substring(0, halfLen)
.split('')
.every((c, i) => c === s[s.length - 1 - i]);
};比較好的方法是使用 Manacher’s 演算法
概念就是用一個陣列 z，z[i] = 當 i 為中心點時最長的回文，範例：
s = [ a b a c a b a d ]
z = [ 1 2 1 4 1 2 1 1 ]Manacher 的概念就是在迭代時應用回文的特性 - 左右對稱，來減少已經運算過的值， 意思是說
i = [ 0 1 2 3 4 5 6 7 ]
s = [ a b a c a b a d ]
z = [ 1 2 1 3 1 * ]當我迭代到 b 的時候會發現前面的 c 長度為 4， 回文是 abacaba，包含著即將要算的 b
那麼 b 的值最少就是
min("abacaba"，c 為中心的映射值 2(i = 1 的 b), b 到 "abacaba" 最右邊距離 的 最小值 1)。
還有這個方法不適用偶數長度的回文(偶數的中心不存在)，
方法是先把字串中間穿插不會出現的字元 @ 是在比較時拿來處理陣列邊界)
/* beats 97.84 % */
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if (s === null || s.length <= 1) return s;
const joinDotStr = `@.${s.split('').join('.')}.`;
let center;
const z = manacher(joinDotStr, (maxIndex) => center = maxIndex);
return joinDotStr
.substring(center - (z[center] - 1), center + z[center])
.split('.').join('')
};
const manacher = (s, callback) => {
const z = Array(s.length).fill(1);
let nowMax = 0;
let mid = 0;
let right = 0;
for (let i = 1; i < s.length; i += 1) {
z[i] = i < right ? Math.min(z[2* mid - i], right - i) : 1; // mirror = mid - (i - mid)
while (s[i + z[i]] === s[i - z[i]]) z[i] += 1;
if (z[i] >= z[nowMax]) callback(nowMax = i);
if (z[i] + i > right) {
mid = i;
right = i + z[i];
}
}
return z;
};