最长回文子串|博客系列
# 题目描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 一🌰：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
@前端进阶之旅: 代码已经复制到剪贴板
示例二🌰：
输入： "aafddfa"
输出： "afddfa"
@前端进阶之旅: 代码已经复制到剪贴板
示例三🌰：
输入： "abda"
输出： "a"
注意： "abda"并不是回文字符串，"abba"才是
@前端进阶之旅: 代码已经复制到剪贴板
所谓回文字符串就比如是：“上海自来水来自海上”，正读反读都是一样的。
# 解题思路1
暴力破解法：
（不推荐）
- 将输入的字符串转换为数组；
- 嵌套两层
for循环遍历数组，比较每一种情况下的字符串与它的反转字符串是否相同，若是相同则表明它为回文； - 比较出长度最长的回文子串。
暴力解决法最容易理解，但是所需的时间复杂度太大，在leetCode上允许只通过了一半的测试用例，因此不推荐使用。
# coding1
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if (!s) return ''
if (s.length <= 1) return s
let sArr = s.split(''),
maxStrs = [],
currentStrs = [];
for (let i = 0; i < sArr.length; i++) {
for (let j = i; j < sArr.length; j++) {
currentStrs = sArr.slice(i, j + 1)
if (currentStrs.join('') === currentStrs.reverse().join('')) {
maxStrs = maxStrs.length > currentStrs.length ? maxStrs : currentStrs
}
}
}
return maxStrs.join('')
};
@前端进阶之旅: 代码已经复制到剪贴板
# 解题思路2
三、中心扩展法：
（相对容易理解且效率高）
我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n−1 个这样的中心。
为什么中心是2n-1而不是n ? 比如有字符串abcba，这时回文子串是abcba，中心是c；
又有字符串adccda，这时回文子串是adccda，中心是cc。
由此可见中心点既有可能是一个字符，也有可能是两个字符，当中心为一个字符的时候有n个中心，当中心为两个字符的时候有n-1个中心，所以一共有2n-1个中心。
- 考虑字符串长度为0和1的情况；
- 考虑字符串长度为2的情况，若为2则判断这个字符串是不是回文字符串；
for循环字符串，比较第i项和第i+1项是否相同(s[i]是否等于s[i+1])；- 若是相同则表示
s[i] + s[i+1]为偶数的回文中心，因此应该继续比较i-1和i+2项；比如给定字符串abba，i为1时，我们已经知道了s[i] + s[i+1]，此时应该以bb为中心向左右进行扩展比较s[i-1]和s[i+2]项； - 若是不同则表示字符串可能是为寄数的回文中心，因此应该以
s[i]为中心向左右进行扩展比较s[i-1]和s[i+1]项； - 每次
for循环中比较上面得到的寄数回文字符串和偶数回文字符串，取较长的； - 每次
for循环中比较之前记录下最长的回文字符串和这次的回文字符串，取较长的； for循环之后即可得到最长回文字符串；
中心扩展法的核心就是通过找到回文中心，然后以该中心向左右两边扩展来查找。
复杂度分析
时间复杂度：O(n^2)，由于围绕中心来扩展回文会耗去 O(n) 的时间，所以总的复杂度为 O(n^2)
空间复杂度：O(1)。
# coding2
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
if (!s) return ''
if (s.length === 1) return s;
if (s.length === 2) return s[0] === s[1] ? s : s[1];
let maxStr = '',
len = s.length;
for (let i = 0; i < len; i++) {
let even = '', // 定义偶数中心回文
odd = ''; // 定义奇数中心回文
if (s[i] === s[i + 1]) { // 若是偶数中心回文
let evenIndex = center(s, i - 1, i + 2); // 比较中心的前一项和后一项
even = s.slice(evenIndex.left, evenIndex.right)
}
let oddIndex = center(s, i - 1, i + 1); // 奇数中心回文
odd = s.slice(oddIndex.left, oddIndex.right);
let longer = even.length > odd.length ? even : odd; // 比较奇、偶
maxStr = maxStr.length > longer.length ? maxStr : longer
}
return maxStr
}
// 中心扩展
function center(s, left, right) {
let len = s.length;
while (left >= 0 && right < len && s[left] === s[right]) {
left--;
right++;
}
return { left: left + 1, right: right }
}
@前端进阶之旅: 代码已经复制到剪贴板
