5. 最长回文子串

穷举

记录当前要穷举的长度，从可能的最大长度开始。

这样可以在第一次遇到回文串的时候直接返回结果

function longestPalindrome(s: string): string {
  let len = s.length // 当前遍历的长度

  // 将当前长度遍历完
  while (len) {
    let left = 0
    let right = left + len

    // 遍历指定长度就是滑动窗口
    // 只不过是窗口大小不动
    while (right <= s.length) {
      // 优化方式：不要每次都 slice 字符串，有开销
      // 可以传入 s, left 和 right
      // 当是回文字符串的时候再 slice
      const str = s.slice(left, right)

      // 因为是从长度递减的检查
      // 所以第一次碰到的就是结果
      if (isPalindrome(str)) {
        return str
      }

      left += 1
      right += 1
    }

    // 检查下一个长度
    len -= 1
  }
}

/**
 * 判断字符串是否是回文串
 */
function isPalindrome(s: string): boolean {
  let left = 0
  let right = s.length - 1

  // 一直到 left >= right 遍历完
  while (left < right) {
    // 如果遇到不相等的说明不是回文串
    if (s[left] !== s[right]) {
      return false
    }

    // 判断下一个对应的字符
    left += 1
    right -= 1
  }

  return true
}

中心扩展法

回文串从中心开始，两边都是对称的。

所以可以从遍历一次，每个点都当作中心点

function longestPalindrome(s: string): string {
  // 回文串从中心往两边扩展也都是回文串
  // 所以可以遍历字符串一次，每个位置都作为中心去获取回文串

  let start = 0 // 回文串的起始位置
  let maxLen = 0 // 回文串长度

  // 遍历所有的字符
  for (let i = 0; i < s.length; i += 1) {
    // 一个字符一定是回文串
    // 一个以上就需要进行判断了
    // 偶数长度的话中心是两个数字
    // 奇数是一个
    // 所以两种都要检测
    // 才能保证不漏结果

    // 如果剩下的长度不可能超过现在的长度
    // 直接 break
    // 这个也可以优化大量时间
    if (maxLen >= s.length * 2 - i) {
      break
    }

    // 检测奇数
    const oddLen = getPalindromeLength(s, i, i)

    // 当新的长度比现有的更长的时候，才进行更新
    if (oddLen > maxLen) {
      const step = (oddLen - 1) / 2
      start = i - step
      maxLen = oddLen
    }

    // 检测偶数
    const evenLen = getPalindromeLength(s, i, i + 1)

    // 当新的长度比现有的更长的时候，才进行更新
    if (evenLen > maxLen) {
      const step = evenLen / 2 - 1

      start = i - step
      maxLen = evenLen
    }
  }

  return s.slice(start, start + maxLen)
}

/**
 * 获取回文串字符串的区间
 * 返回回文字符串的 len
 * 当前方法是依次优化出来的 str.slice -> [start, end] -> len
 * 第一次减少 slice 开销，第二次减少数组开销
 *
 * 两个中心点是为了兼容奇数和偶数的回文字符串
 * @param s 字符串
 * @param start 中心点1 开始位置 
 * @param end 中心点2 开始位置 
 */
function getPalindromeLength(s: string, start: number, end: number): number {
  let left = start
  let right = end

  // 必须在字符串内
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    // 判断下一个对应的字符
    left -= 1
    right += 1
  }

  // 因为结束的时候左右都会多走一步
  // 所以结果为 right - left + 1 - 2
  return right - left - 1
}