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

    示例 1：

    输入: “babad”
    输出: “bab”
    注意: “aba” 也是一个有效答案。
    示例 2：

    输入: “cbbd”
    输出: “bb”

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/longest-palindromic-substring

    思路：
    使用动态规划：有
    dp[i][i] = true
    dp[i][j] = s[i]==s[j]&&dp[i+1][j-1]
    中心拓展法则枚举每个点为回文串中点，向两侧扩展。
    复杂度分析：
    动态规划：时间复杂度O(n)空间复杂度O(n)
    image.png
    中心拓展法:时间复杂度O(n)，空间复杂度O(1)。 中心扩展法的复杂度实际比动态规划低的多，每个回文中心最多会向外扩展O(n)次
    image.png

    1. //动态规划
    2. var longestPalindrome = function (s) {
    3.     let n = s.length;
    4.     if (n === 0) {
    5.         return "";
    6.     }
    7.     let dp = new Array(n).fill(undefined).map(() => new Array(n).fill(false));
    8.     let ans = '';
    9.     for (let i = n - 1; i >= 0; i--) {
    10.         for (let j = i; j < n; j++) {
    11.             if (s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
    12.                 dp[i][j] = true;
    13.                 if(j-i+1>ans.length){
    14.                       ans = s.substring(i,j+1)
    15.                 }
    16.             }
    17.         }
    18.     }
    19.     return ans;
    20. };
    21. //中心扩展法
    22. var longestPalindrome = function(s) {
    23.     let length = s.length;
    24.     if(length < 2){
    25.         return s;
    26.     }
    27.     let [start, maxLength] = [0, 1];
    29.     //判断一个字符串是否为回文
    30.     function isPalindrome(left, right){
    31.         while(left>=0 && right<length && s[left] === s[right]){
    32.             if(right-left+1>maxLength){
    33.                 maxLength = right-left +1;
    34.                 start = left;
    35.             }
    36.             left --;
    37.             right ++;
    38.         }
    39.     }
    40.     for(let i=0; i<length; i++){
    41.         isPalindrome(i-1, i+1);
    42.         isPalindrome(i,i+1);
    43.     }
    44.     return s.substring(start, start + maxLength);
    45. };