题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

测试用例

示例 1：

• 输入：s = "babad"
• 输出："bab"
• 解释："aba" 同样是符合题意的答案。

示例 2：

• 输入：s = "cbbd"
• 输出："bb"

思路

中心扩散 + 双指针

代码实现

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let res = "";
    for(let i = 0; i < s.length; i ++){
        // 分成奇偶长度来判断 —— 因为中心点可以是一个，也可以是两个
        // 比如 aba 中心点是 b 往两边扩散
        // abba 的中心点就 bb 往两边扩散
        const s1 = find(s, i, i);
        const s2 = find(s, i, i + 1);
        
        res = res.length <= s1.length ? s1 : res;
        res = res.length <= s2.length ? s2 : res;
    }
    
    return res;
};

function find(s, l, r){

    // 从中心点往外扩散 —— 找长度最大的回文子串
    while(l >= 0 && r < s.length && s[l] === s[r]){
        l --;
        r ++;
    }

    return s.slice(l + 1, r);
}