[LeetCode]. 5.最长回文串

[MagicalBridge]

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

示例 1:

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

示例 2：

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

示例 3：

  输入：s = "a"
  输出："a"

示例 4：

  输入：s = "ac"
  输出："a"

中心扩散法

主要思路是枚举所有可能的回文子串的中心位置，在枚举的时候需要考虑回文子串的奇偶性，对于奇数回文子串来说，中心位置是一个字符，对于偶数来说，中心位置是两个相邻的字符。

需要注意的是，在枚举的过程中需要记录最长回文子串的相关变量。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  // 首先处理边界条件
  if (s === null || s === undefined) {
    return
  }
  if (s.length < 2) {
    return s
  }
  // 记录最大的长度
  let maxlen = 0;
  let begin = 0;
  let len = s.length;

  // 遍历字符串,分别以奇数和偶数的维度来寻找回文子串
  for (let i = 0; i < len; i++) {
    // 借助函数拿到以奇数和偶数分别为中心的长度
    let oddmaxlen = helper(s, i, i);
    let evenmaxlen = helper(s, i, i + 1);
    let currentlen = Math.max(oddmaxlen, evenmaxlen);

    // 更新最大长度
    if (currentlen > maxlen) {
      maxlen = currentlen
      begin = i - Math.floor((maxlen - 1) / 2)
    }
  }
  return s.substring(begin, begin + maxlen)
};
/**
判判断是否是回文串的辅助函数
接收三个参数 字符串本身，中心点
*/
function helper(s, left, right) {
  // 当left = right 的时候，回文中心是一个字符，回文串的长度是奇数
  // 当right = left + 1 的时候，此时，回文中心是两个字符，回文串的长度是偶数
  while (left >= 0 && right < s.length) {
    // 左边界向左，右边界向右，逐个比对，直到不相同为止。
    if (s.charAt(left) === s.charAt(right)) {
      left--;
      right++;
    } else {
      break
    }
  }
  // 跳出循环的时候 恰好满足 s.charAt(left) !== s.charAt(right)
  // 回文串的长度是 right - left + 1 - 2 = right - left -1;
  // 5 6 7 8 9 总共几个数 9-5+1 = 5个数 去掉 5和 9 剩下 4个 一个道理
  return right-left -1;
}