【LeetCode刷题】最长回文子串-Toy模板网

这篇具有很好参考价值的文章主要介绍了【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的情况：

j=i+1;j<s.length;j++	j=i;j<s.length;j++
1	0
2	1
3	2
	3

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

思路二：双指针

left指针前移，right后移，若left指向的元素和right指向的元素相同，构成新的回文串。然后通过比较，找出最长的回文串。文章来源地址https://www.toymoban.com/news/detail-422281.html

/**
 * @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+1
    let maxStr = s.slice(left + 1, right);
    if (maxStr.length > max.length) max = maxStr;
  }
  return max;
};