LeetCode第5题.最长回文子串 JavaScript题解

题目描述:

给定一个字符串，要求这个字符串当中最长的回文串。

示例

Input: "babad"
Output: "bab"
复制代码

Note: “aba” is also a valid answer.

Input: "cbbd"
Output: "bb"
复制代码

解题思路：

1、先判断边界情况 s 长度小于2则返回原字符串，并设立字符串初始位置，以及最大长度

2、如果s的长度不小于2，则开始以i为中心进行判断，因为回文的形式有 ‘aba’ ‘bbbb’这两种情况，所以需要以i-1，i+1 （单元素为中心）和i，i+1（双元素为中心）进行检查，使用检查函数

3、编写检查函数，参数两个一左一右left 和 right 当 left>=0时左边界不越界 以及 right < s.length 右边界不越界 以及 s[left] === s[right] 三个条件成立时则 进行字符串长度的判断
如果字符串大于最大长度，则赋值最新的最大长度，以及赋值初始位置为left，随后再left– right++ 位置朝两边扩散，直至边界条件不成立

4、检查完两种情况则返回 以初始位置为起点 ，初始位置 与 最大长度的和为终点的 字符串

JS解题代码：

var longestPalindrome = function(s) {
     if( s.length < 2){
         return s   
     }else{
          let start = 0;
          let maxlength =1;
          function getHuiString(left,right){
              while(left>=0 && right < s.length && s[left] === s[right]){
                  if(right - left + 1 > maxlength){
                      maxlength = right - left + 1
                      start = left
                  }
                  left--;
                  right++;
              }  
          }
          for(var i=0;i<s.length;i++){
              getHuiString(i-1 , i+1)
              getHuiString(i,i+1)
          }
          return s.substring(start ,start+maxlength)
     }
};

复制代码