Open
Description
给你一个字符串 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;
}