第五題:最長回文子串【leetcode】

給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。輸入: 'babad'
輸出: 'bab'
注意: 'aba' 也是一個有效答案。

難度：中等

連結：https://leetcode-cn.com/problems/longest-palindromic-substring/

方法一、暴力破解法，第一層循環從字符串開頭開始遍歷，第二層字符串從結尾開始遍歷，當找到與開頭的字符一樣的時候，對比它們之間的字符串，將區間字符串逐一對比，如果是回文且比臨時最大回文字符串的長度對比，如果大於重新賦值最大回文字符串，如果小於跳過。將區間字符串逐一對比，如果不是回文跳過，繼續執行上述步驟。當剩餘字符串小於最大回文字符串，循環結束，返回最大回文字符串。

var longestPalindrome = function(s) {
let isWell = true;
let maxStr = s[0] || '';
for(let i = 0, l = s.length; i < l; i++){
let word = s[i];
if(l - i > maxStr.length){
for(let j = l; j > i; j--){
if(word == s[j]){
isWell = true;
if(isWell){
for(let k = i, kl = i + parseInt((j - i + 1)/2); k < kl; k++){
if(s[k]!=s[j - k + i]){
isWell = false;
}
}
if(isWell){
if(maxStr.length < s.substring(i, j + 1).length){
maxStr = s.substring(i, j + 1);
break;
}
}
}
}else{
isWell = false;
}
}
}else{
break;
}
}
return maxStr;
}

longestPalindrome('qianduankak');

方法二、 中間拓展法，將子串分為單核和雙核的情況，單核即指子串長度為奇數，雙核則為偶數；遍歷每個除最後一個位置的字符index(字符位置)，單核：初始low = 初始high = index，low和high均不超過原字符串的下限和上限；判斷low和high處的字符是否相等，相等則low++、high++（雙核：初始high = 初始low+1 = index + 1）；每次low與high處的字符相等時，都將當前最長的回文子串長度與high-low+1比較。後者大時，將最長的回文子串改為low與high之間的；重複執行，直至high-low+1 等於原字符串長度或者遍歷到最後一個字符，取當前截取到的回文子串，該子串即為最長的回文子串。

var longestPalindrome = function (s) {
if (!s || s.length < 2) {
return s;
}
let start = 0, end = 0;
let n = s.length;
let centerExpend = (left, right) => {
while (left >= 0 && right < n && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1;
}
for (let i = 0; i < n; i++) {
let len1 = centerExpend(i, i);
let len2 = centerExpend(i, i + 1);
let maxLen = Math.max(len1, len2);
if (maxLen > end - start) {
start = i - ((maxLen - 1) >> 1);
end = i + (maxLen >> 1);
}
}
return s.substring(start, end + 1);
};
longestPalindrome('qianduankak');

方法三、Manacher算法，Manacher於發現了一種線性時間算法，可以在列出給定字符串中從任意位置開始的所有回文子串。回文串（palindromic string）是指這個字符串無論從左讀還是從右讀，所讀的順序是一樣的；簡而言之，回文串是左右對稱的。

前端咖，值得關注，在看哦