5. 最长回文子串
力扣 15. 给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
- 解法一（自己写的）
- 核心：在字符串循环中，先找到重复的字符位置，从最远位置开始，用指针往回看是否满足回文
- 因为多次循环，所以设置了一些退出条件：回文判断由远到近，找到一个就不用再找了，因为不会再找到当前字符更长的子串
时间：464ms 内存：46.6M
var longestPalindrome = function(s) {
// 边界条件
if(!s || s.length < 2) {
return s;
}
// 用于存储当前找到的最大长度的 str
let currentStr = '';
let currentMax = 0; // 当前最大长度
const len = s.length;
for(let i = 0; i < len; i++) {
const item = s[i];
const index = i;
// 当前项为 item - 找到右侧和 item 相等的所有字符位置
const itemEqualIndexs = [];
let restIndex = index + 1;
while(restIndex < len) {
if(s[restIndex] === item) {
// 字符位置由大到小排列
itemEqualIndexs.unshift(restIndex);
}
restIndex++;
}
// 当前字符没有重复的 - 没有回文子串 && 且当前没有子串 -> 第一次执行
if(!itemEqualIndexs.length && currentMax === 0) {
currentMax = 1;
currentStr = item;
}
// 利用指针遍历循环当前子串是否满足回文，不满足则继续使用下一个字符位置进行判断
itemEqualIndexs.forEach((equal) => {
let L = index;
let R = equal;
// 先判断当前 item 可以产生的字符串长度是否可能大于 currentMax
if((R - L + 1) < currentMax) {
return
}
while(s[L] === s[R] && L < R) {
L++;
R--;
}
// 代表符合回文数
if(L >= R) {
currentStr = s.slice(index, equal + 1);
currentMax = currentStr.length;
// 在当前字符，已经找到最长回文子串时，不去计算其他子串
return
}
})
}
return currentStr;
};
- 解法二：中心扩散法
- 一开始看了好久，核心在于，传入 helper 的参数，i和i 或者 i和i+1，helper 函数中，是以这两点作为起点，去找满足回文的子串，这样就只要循环一次就能够找到最长子串了 -> 从中心点开始扩散寻找，效率高很多
时间：100ms 内存：41.6M
var longestPalindrome = function(s) {
if (s.length<2){
return s
}
let res = ''
for (let i = 0; i < s.length; i++) {
// 回文子串长度是奇数
helper(i, i)
// 回文子串长度是偶数
helper(i, i + 1)
}
function helper(m, n) {
while (m >= 0 && n < s.length && s[m] == s[n]) {
m--
n++
}
// 注意此处m,n的值循环完后 是恰好不满足循环条件的时刻
// 此时m到n的距离为n-m+1，但是mn两个边界不能取 所以应该取m+1到n-1的区间 长度是n-m-1
if (n - m - 1 > res.length) {
// slice也要取[m+1,n-1]这个区间
res = s.slice(m + 1, n)
}
}
return res
};