5.最长回文子串.md

5.最长回文子串

/*
 * @lc app=leetcode.cn id=5 lang=typescript
 *
 * [5] 最长回文子串
 */

// @lc code=start
function longestPalindrome(s: string): string {}
// @lc code=end

5.最长回文子串 - 从递归逐步优化成动态规划

解法 1: 动态规划

• 时间复杂度:

• 空间复杂度:

• 动态规划

• 状态: dp[i][j] 以第 i 个字符结尾的回文子串长度

• 递推公式:

  • s[i]===s[i-dp[i-1][j]-1]: dp[i][j] = dp[i-1][j]+2

• 边界: dp[i]=[0,1]

看很多题解中,不管是动态规划(dp[i][j]表示子串s[i..j]是否为子串),还是中心扩散,第二层的遍历需要一个一个字符的去遍历

而在这个动态规划中,dp[i][j]表示的是以s[i]结尾的回文子串的集合,在大多数情况下,这个集合的数量肯定会小于一个个字符去遍历的长度,而dp[i]只需要从dp[i-1]中转移,不必要一个个字符去遍历,这样会快很多

当然,如果是一些比较极端的例子,比如像aaaaaaa这样的情况,复杂度还是会到 O(n^2)

function longestPalindrome(s: string): string {
  const dp = new Array(s.length).fill(0).map(() => [0, 1])
  let [start, end] = [0, 1]
  for (let i = 1; i < s.length; i++) {
    for (const l of dp[i - 1]) {
      if (s[i] === s[i - l - 1]) dp[i].push(l + 2)
    }
    const len = dp[i][dp[i].length - 1]
    if (len > end - start) [start, end] = [i - len + 1, i + 1]
  }
  return s.slice(start, end)
}

解法 2: 中心扩展法

function longestPalindrome(s: string): string {
  s = s.split('').join('#')
  let left = 0,
    right = 1
  for (let i = 0; i < s.length; i++) {
    let len = 1
    for (let j = i + 1; j < Math.min(s.length, 2 * i + 1); j++) {
      if (s[j] === s[2 * i - j]) len += 2
      else break
      if (len > right - left && s[j] !== '#') {
        left = 2 * i - j
        right = j + 1
      }
    }
  }
  return s.slice(left, right).replace(/#/g, '')
}

解法 3: Manacher 算法

/**
 * @see: https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2#Manacher%E7%AE%97%E6%B3%95
 * @param s 需要判断的字符串
 * @returns
 */
function longestPalindrome(s: string): string {
  s = s.split('').join('#')
  // 记录答案的左右坐标
  let [resLeft, resRight] = [0, 1]
  // 当前能延伸到最右边的中心点和右坐标
  let [center, maxRight] = [0, 0]
  // 记录以 i 为中心的最长回文串,其中心到右边界的长度 (len - 1 / 2)
  const dp: number[] = []

  for (let i = 0; i < s.length; i++) {
    // 合并三种情况,初始化当前点到右边界的长度
    dp[i] = Math.min(dp[2 * center - i] ?? 0, maxRight - i)

    // 如果当前点能刚好延伸到 maxRight,则是第三种情况,其有可能存在更长的回文串,需要进一步判断
    if (i + dp[2 * center - i] === maxRight) {
      for (let j = maxRight + 1; j < Math.min(s.length, 2 * i + 1); j++) {
        if (s[j] !== s[2 * i - j]) break

        // 如果能执行到这,则说明当前中心点 i 的最长回文串右边界位置会超过之前的 maxRight,所以需要更新之前的值
        ;[maxRight, center, dp[i]] = [j, i, dp[i] + 1]
        if (s[j] !== '#' && dp[i] * 2 + 1 > resRight - resLeft) [resLeft, resRight] = [i - dp[i], i + dp[i]]
      }

      // 记录更长的返回值
    }

    // 这种情况,说明 i 已经到了最右边界,并且以当前点 i 为中心的回文串只包含自身,所以将 center 和 maxRight 右移
    if (i === maxRight) center = ++maxRight
  }

  // 返回答案,其中 resRight 记录的是答案的最右边界,使用 slice 取值时,需要加 1
  return s.slice(resLeft, resRight + 1).replace(/#/g, '')
}

Case

test.each([
  { input: { s: 'babad' }, output: 'bab' },
  { input: { s: 'cbbd' }, output: 'bb' },
  { input: { s: 'a' }, output: 'a' },
  { input: { s: 'ac' }, output: 'a' },
])('input: s = $input.s', ({ input: { s }, output }) => {
  expect(longestPalindrome(s)).toEqual(output)
})