5. 最长回文子串

[mengjian-github]

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

 

示例 1：

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

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

[mengjian-github]

暴力解法比较容易想到，枚举所有的字串，找出符合回文串最大长度的那个
但是正常的枚举会超出LeetCode时间限制，这里j指针可以从后往前枚举，找到回文串跳出循环，这个剪枝的处理可以AC：

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    const isPalindrome = (a) => a.split('').reverse().join('') === a;
    let result = s[0];

    for (let i = 0;i < s.length; i++) {
        for (let j = s.length - 1; j > i; j--) {
            if (s[j] === s[i]) {
                const target = s.slice(i, j + 1);
                if (isPalindrome(target)) {
                    if (target.length > result.length) {
                        result = target;
                    }
                    break;
                }
            }
        }
    }

    return result;
};

[mengjian-github]

在暴力解法中，每次都要去判断是否是回文串，比较耗时，可以采用中心扩散的**，假设当前循环中的字符为中心，有两种情况：

• 当前点为中心，从两边扩散寻找奇数最长回文串
• 以当前点和下个点为中心，从两边扩散寻找偶数最长回文串

这样可以把时间复杂度降低为O(n2)：

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
   
    let result = '';

    for (let i = 0;i < s.length; i++) {
        const odd = getOddMaxStr(s, i);
        const even = getEvenMaxStr(s, i);

        const maxResult = odd.length > even.length ? odd : even;

        result = maxResult.length > result.length ? maxResult : result;
    }

    function getOddMaxStr(s, i) {
        // 以当前字符为中心，往两边扩散
        let a = i - 1;
        let b = i + 1;
        let r = s[i];

        while(s[a] && s[b] && s[a] === s[b]) {
           r = s.slice(a, b + 1);
           a--;
           b++;
        }

        return r;
    }

    function getEvenMaxStr(s, i) {
        // 以当前字符和下个字符为中心，往两边扩散
        let a = i - 1;
        let b = i + 2;
        let r = s.slice(i, i+2);

        // 中间的两个字符必须要相同
        if (s[i] !== s[i+1]) {
            return s[i];
        }

        while(s[a] && s[b] && s[a] === s[b]) {
           r = s.slice(a, b + 1);
           a--;
           b++;
        }

        return r;
    }

    return result;
};

[mengjian-github]

另一种思路，由于判断回文串可以拆分为子问题：
一个回文串的判断条件是，当首尾两个字符相等，且其中的子串是回文串
这样可以根据递推关系编写动态规划算法，注意dp数组填充，要先填充i+1和j-1的位置，才能根据递推关系依次算出子串：

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
   
    let result = '';

    // 初始化dp二维数组
    const dp = [];
    for (let i = 0; i < s.length; i++) {
        dp[i] = [];
    }

    for (let j = 0; j < s.length; j++) {
        // j不动，i往下减，这样可以先计算出i+1和j-1
        for (let i = j; i >= 0; i--) {
            if (i === j) {
                // 一个元素，肯定是回文串
                dp[i][j] = true;
            } else if (j - i === 1) {
                // 两个元素，若相等就是回文串
                dp[i][j] = (s[i] === s[j]);
            } else {
                // 大于两个元素，判断两边相等，并且内部是不是回文串
                dp[i][j] = (s[i] === s[j] && dp[i+1][j-1]);
            }
            if (dp[i][j]) {
                // 如果是回文串的话，尝试更新下result
                const r = s.slice(i, j + 1);
                result = result.length > r.length ? result : r;
            }
        }
    }

    return result;
};