回文字符串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"

输出: "bab"

注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"

输出: "bb"

分析

本题最容易想到的一种方法应该就是中心扩散法。

中心扩散法怎么去找回文串？从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。

举个例子，str = "acdbbdaa"。我们需要寻找从第一个b（位置为3）出发最长回文串为多少。怎么寻找？

首先往左寻找与当期位置相同的字符，直到遇到不相等为止。

然后往右寻找与当期位置相同的字符，直到遇到不相等为止。

最后左右双向扩散，直到左和右不相等。如下图所示:

每个位置向两边扩散都会出现一个窗口大小（len）。如果len>maxLen(用来表示最长回文串的长度）。则更新maxLen的值。

因为我们最后要返回的是具体子串，而不是长度，因此，还需要记录一下maxLen时的起始位置（maxStart），即此时还要maxStart=len。

function longestPalindrome(str) {
    if (!str || str.length < 2) {
        return str;
    }
    const strLen = str.length;
    let maxStart = 0;
    let maxEnd = 0;
    let maxLen = 1;
    const cc = [];
    for (let r = 1; r < strLen; r++) {
        for (let l = 0; l < r; l++) {
            cc[l] = [];
            cc[l][r] = false;
            if (str.charAt(l) === str.charAt(r) && (r - l <= 2 || cc[l + 1][r - 1])) {
                cc[l][r] = true;
                if (r - l + 1 > maxLen) {
                    maxLen = r - l + 1;
                    maxStart = l;
                    maxEnd = r;
                }
            }
        }
    }
    return str.substring(maxStart, maxEnd + 1);
}
var longestPalindrome = function (s) {
    if (!s || s.length < 2) {
        return s;
    }
    var s_f = s.split('').reverse().join('');
    var resultStr = s[0];
    var maxLen = 1;
    var tmpLen = 1;
    var maxStrIndex = 0;
    var len = s.length;
    //判断字符串是否回文
    function ispalinerome(i, r) {
        if (len - i - 1 == r - tmpLen + 1) {
            return true
        }
        return false;
    }
    //初始化二维数组
    var len = s.length;
    var arr = new Array(len);
    for (var i = 0; i < len; i++) {
        arr[i] = [];
        for (var r = 0; r < len; r++) {
            arr[i][r] = 0
        }
    }
    for (var i = 0; i < len; i++) {
        for (var r = 0; r < len; r++) {
            if (s[i] == s_f[r]) {
                if (i == 0 || r == 0) {
                    arr[i][r] = 1
                } else {
                    arr[i][r] = arr[i - 1][r - 1] + 1
                    tmpLen = arr[i][r]
                }
                if (tmpLen > maxLen && isPalinerome(i, r)) {
                    maxStrIndex = r;
                    maxLen = tmpLen;
                    resultStr = s.substring(i - tmpLen + 1, i + 1);
                }
            }
        }
    }
    return resultStr;
};