【LeetCode刷题】最长回文子串

📝个人主页：爱吃炫迈
💌系列专栏：数据结构与算法
🧑‍💻座右铭：道阻且长，行则将至💗

题目：最长回文子串

思路一：暴力

枚举每一个子串，找回文串，然后通过比较，找出最长的回文串。

• 会超时

/* @param {string} s* @return {string}*/
var longestPalindrome = function (s) {let len = s.length;if (len <= 1) {return s;}let temp;let temp1;let max = "";for (let i = 0; i < len - 1; i++) {for (let j = i; j < len; j++) {temp = s.slice(i, j + 1);temp1 = temp.split("").reverse().join("");if (temp1 == temp) {if (temp.length > max.length) {max = temp;}}}}return max;
};

• 学习更多的JavaScript字符串方法，例如上面代码中用到的split(),join()等
• 学习更多的JavaScript数组方法，例如上面diam中用到的reverse()等
• j为什么从i开始，而不是从i+1开始？

答：slice截取字符串时，是[i,j)，左闭右开的。

举个栗子：

let s = "abcd";
console.log(s.slice(0, 1));//a
console.log(s.slice(0, 2));//ab
console.log(s.slice(0, 3));//abc
console.log(s.slice(0, 4));//abcd

i=0的情况：

此时再执行slice(i,j+1)

思路二：双指针

left指针前移，right后移，若left指向的元素和right指向的元素相同，构成新的回文串。然后通过比较，找出最长的回文串。

/* @param {string} s* @return {string}*/
var longestPalindrome = function (s) {let max = "";for (let i = 0; i < s.length; i++) {//  分奇偶，一次遍历，每个字符位置都可能存在奇数或偶数回文helper(i, i);helper(i, i + 1);}function helper(left, right) {// 定义左右双指针while (left >= 0 && right < s.length && s[left] === s[right]) {left--;right++;}// 拿到回文字符， 注意:上面while满足条件后多执行了一次，所以需要left+1, right-1+1let maxStr = s.slice(left + 1, right);if (maxStr.length > max.length) max = maxStr;}return max;
};

• 为什么拿到回文串后right指针要right-1+1
  答：因为while多执行了一次，所以right-1；又因为slice是[i,j)左闭右开的，所以right-1+1