(找)最长回文串

[wangjs-jacky]

输入：s = "babad" 输出："bab"

[wangjs-jacky]

对于找回文串，需要构造由内向外扩展的验证函数

function spreadfromCenter(l, r) {
  while (l >= 0 && r <= s.length) {
    if (s[l] === s[r]) {
      l--;
      r++;
    } else {
      break;
    }
  }
}

如果是验证回文字符串的话，while 的循环条件需变为 left < right

// 第1步：将验证回文子符串编写为一个函数
function isPalindrome(left, right) {
  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    } else {
      left++;
      right--;
    }
  }
  return true;
}

[wangjs-jacky]

找的过程中，可能符合条件的回文串很多，但是根据题意需要输出最大的一个字符串。

使用 start + maxLength 的方式输入，输出 s.substring(start,start+maxlength)

function spreadfromCenter(l, r) {
  while (l >= 0 && r <= s.length) {
    if (s[l] === s[r]) {
      if (r - l + 1 > maxlength) {
        start = l;
        maxlength = r - l + 1;
      }
      l--;
      r++;
    } else {
      break;
    }
  }
}

const longestPalindrome = (s) => {
  let start = 0;
  let maxlength = 1;
  for (let i = 0; i < s.length; i++) {
    /* 考虑：c[aba]d  */
    spreadfromCenter(i, i + 1);
    /* 考虑：c[abba]d（中心点bb） */
    spreadfromCenter(i - 1, i + 1);
  }

  return s.substring(start, start + maxlength)
};

console.log(longestPalindrome("babad"))