5

题目

方法一：暴力解法循环两层遍历，遍历每一个字串，然后对每一个字串进行判断是否是回文字符串。时间复杂度O(n^3)，空间复杂度O(1)。

var longestPalindrome = function(s) {
  let len = s.length;
  if(len<2)return s;
  let maxLen = 1;
  let begin = 0;
  for(let i=0;i<len-1;i++){
    for(let j=i+1;j<len;j++){
      if(j-i+1>maxLen&&isJudge(s,i,j)){
        maxLen = j-i+1;
        begin = i;
      }
    }
  }
  return s.substring(begin,begin+maxLen);
};

function isJudge(s,i,j){
  while(i<j){
    if(s[i]!==s[j]){
      return false;
    }
    i++;
    j--;
  }
  return true;
}

方法二：中心扩散法遍历每一个长度为奇数或偶数的字串中心，然后向两边扩散。

var longestPalindrome = function(s) {
  let len = s.length;
  if(len<2)return s;
  let maxLen = 1;
  let big = 0;
  for(let i=0;i<len-1;i++){
    let ou = findJudge(s,i,i+1,len);
    let ji = findJudge(s,i,i,len);
    let maxTemp = Math.max(ou,ji);
    if(maxTemp>maxLen){
      maxLen = maxTemp;
      big = i - Math.floor((maxLen-1)/2);
    }
  }
  return s.substring(big,big + maxLen);
};

function findJudge(s,left,right,len){
  while(left>=0&&right<len){
    if(s[left]===s[right]){
      left--;
      right++;
    }else{
      break;
    }
  }
  return right - left + 1 - 2;
}