5.md

Leetcode 5. 最长回文子串

5. 最长回文子串

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  const length = s.length; // 字符串的长度，避免重复计算

  // 计算字符串在 left - right 区间是否包含回文字符串
  const genLen = function (left, right) {
    while (left >= 0 && right < length) {
      if (s[left] !== s[right]) { // 左侧字符不等于右侧字符，不是回文字符串，中断循环
        break;
      }
      left--;
      right++;
    }
    // 返回 left 与 right 之间的数字个数，以及 left 的下标
    // 注意，这里的 left 和 right 组成的字符串已经不是回文字串了，因为已经不符合要求被 break 了。所以实际上，left++, right-- 以后才是当前的回文串
    return [right - left - 1, left + 1];
  }

  let max = 0; // 最长回文字串的长度
  let start = 0; // 最长回文字串的起始下标
  // 遍历字符串
  for (let i = 0; i < length; i++) {
    // 回文字串有单数、双数之分，分别计算单数、双数的情况，取更大的值
    let odd = genLen(i, i);
    let even = genLen(i, i + 1);
    let current = Math.max(odd[0], even[0]);
    // 当前回文串比历史的更大
    if (current > max) {
      max = current;
      // 取更长回文字串的起始下标
      start = odd[0] > even[0]? odd[1]:even[1];
    }
  }
  return s.substr(start, max);
};

console.log(longestPalindrome("babad"));