5. 最长回文子串

题目

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

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

思路　中心扩展法

对于长度为n的字符，有2n-1个中心。遍历中心扩展两边相等最大长度，即可得到最长子串

Javascript解法

**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let len = 0
    let str = ''
    for (let index = 0; index < s.length; index++) {
      let len1 = getPotentialLongest(s, index, index)
      let len2 = getPotentialLongest(s, index, index + 1)

      if( len1 > len && len1 >= len2){
        len = len1
        // 奇数长度
        str = s.substr(index-Math.floor(len/2), len) 
      } else if(len2 > len && len2 > len1){
        len = len2
        // 偶数长度
        str = s.substr(index+1-len/2, len)
      }
    }
    return str
}

function getPotentialLongest(s, left, right){
  let len = 1
  while(left >= 0 && right < s.length){
    if( s[left] === s[right]) {
      len = right - left + 1
      left -- 
      right ++
    }
    else {
      break
    }
  }
  return len
}