https://leetcode-cn.com/problems/longest-palindromic-substring/
点击查看【bilibili】

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例：

  1. 输入: "babad"
  2. 输出: "bab"
  3. 注意: "aba" 也是一个有效答案。
  1. 输入: "cbbd"
  2. 输出: "bb"

解答

回文的意思是正着念和倒着念一样，如：上海自来水来自海上

1.如果字符串长度小于2,直接返回原字符串
2.定义两个变量,一个start存储当前找到的最大回文字符串的起始位置,另一个 **maxLength 记录字符串的长度(**终止位置就是 start+maxLength)
3.创建一个 helper function,进行处理，
判断左边和右边是否越界,
同时最左边的字符是否等于最右边的字符,
如果以上3个三个条件都满足,则判断是否需要更新回文字符串最大长度及最大字符串的起始位置。
然后将left—， right++,继续判断,直到不满足三个条件之一
4.遍历字符串,每个位置调用 helper function两遍
第一遍检查i-1, i+1, 第二遍检查 i+1
(为什么要检查2遍?)
因为有两种情况(有中心的和没有中心的)
image.png
找中心，朝两遍扩散，分为两种情况：

  1. 有中心

  2. 没有中心

    答案

    1. var longestPalindrome = function(s) {
    2.  if(s.length < 2) { //如果字符串长度小于2,直接返回原字符串
    3.      return s;
    4.  }
    5.  let start = 0;
    6.  let maxLength = 1;  // 考虑字符串 ab 的情况，不管怎么查也不会更新maxLength，所以maxLength最小为1
    8.  // 查找中心
    9.  function expandAroundCenter(left, right) {
    10.      // 判断三种情况
    11.      // 左边是否越界
    12.      // 右边是否越界
    13.      // 最左边的字符是否等于最右边的字符
    14.      while(left>=0 && right<s.length && s[left] === s[right]){
    15.          // 是否需要更新回文字符串最大长度及最大字符串的起始位置
    16.          /**
    17.           * right -left +1
    18.           * [a,b,a]  右边2，左边0,0+2=2，而回文最大长度是3，所以+1
    19.           */
    20.          if(right - left +1 > maxLength) {
    21.              maxLength = right -left + 1;
    22.              start = left
    23.          }
    24.          left-- 
    25.          right++
    26.      }
    27.  }
    28.  for(let i=0;i<s.length;i++) {
    29.      expandAroundCenter(i-1,i+1);
    30.      expandAroundCenter(i,i+1);
    31.  }
    32.  return s.substring(start,start+maxLength)
    33. };