5.最長回文子串
給定一個字符串 s，找到 s 中最長的回文子串猜惋。你可以假設(shè) s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案培愁。
示例 2：
輸入: "cbbd"
輸出: "bb"
本題的考點(diǎn)為中心擴(kuò)散算法著摔，即對于字符串，同時做中心擴(kuò)散為單或復(fù)數(shù)的處理定续。這么說起來可能有些復(fù)雜谍咆，舉個栗子。
我們有個字符串私股，abcba 此時中心為 c卧波，若我們還有個字符串 abccba，那么中心應(yīng)該為 cc向兩側(cè)擴(kuò)散庇茫。這個方法有點(diǎn)類似于尋找數(shù)組中的3數(shù)相加等于目標(biāo)數(shù)的問題港粱。
話不多說，上代碼旦签。
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
const length = s.length
let start = 0, end = 0
if(!s.length || s === undefined) {
return ''
}
for(let i = 0; i < length; i++) {
let len1 = getMaxMidwordsLength(s, i, i)//判斷中心為單數(shù)向兩邊擴(kuò)散
let len2 = getMaxMidwordsLength(s, i, i + 1)//判斷中心為雙數(shù)向兩邊擴(kuò)散
let len = Math.max(len1, len2)
if(len > end - start) {
start = i - parseInt((len - 1) / 2)
end = i + parseInt(len / 2)
}
}
return s.substring(start, end + 1)
function getMaxMidwordsLength (words, start, end) {
while (start >= 0 && end < words.length && words.charAt(start) === words.charAt(end)) {
start--
end++
}
return end - start - 1
}
}
一個for循環(huán)內(nèi)調(diào)用兩次while循環(huán)查坪。條件輸入單數(shù)開始和復(fù)數(shù)中心開始。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有宁炫。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)偿曙，非商業(yè)轉(zhuǎn)載請注明出處。
