最长回文子串

Tips

题目类型: 中心扩散法

相关题目:

• 647. 回文子串

题目

给你一个字符串 s, 找到 s 中最长的回文子串.

提示:

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

示例

输入: s = "babad"

输出: "bab" 或者 "aba" 都是符合题意的答案.

题解

该题的思路是中心扩散法. 所谓中心扩散法, 就是找到字符串的一个中点. 往两边扩散, 从少到多, 来判断各个子字符串是否是回文. 所以找中心扩散法的中点是重点.

比如 ababa 这个字符串, 选择最中间的 a 作为中心点, 往两边扩散, 第一次扩散发现 left 指向的是 b, right 指向的也是 b, 所以是回文串, 继续扩散, 同理 ababa 也是回文串.

可以看到我们选择中心的 a 左为中心点, 能扫描到 a, bab, ababa 这几个子字符串, 但它无法扫描到如 abab 这个子字符串. 因此如果我们把 ba(ababa 加粗部分)看作中心点, 往左和右扫描, 就能扫描到 abab 这个子字符串了. 这启发我们中心点的长度可能为 1, 也可能为 2.

因此我们找两个例子:

• str = aba, 中心点应该为 a, b, a, ab, ba
• str = abba, 中心点应该为 a, b, b, a, ab, bb, ba

这样我们就找全了中心点, 也就能覆盖字符串的所有子串了. 我们可以得出规律, centerCount = 2 * str.length - 1. 具体实现直接看代码:

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  const n = s.length
  let max = ''

  for (let i = 0; i < 2 * n - 1; i++) {
    // 上面说到中心点可能有一个(i 为偶数), 也可能为两个(i 为奇数)
    // 故通过如下代码找到中心点
    let left = (i / 2) | 0
    let right = left + (i % 2)

    // 要保证中心点不越界, 并且要从中心点起, 判断左右字符是否相等
    while (left < n && right < n && s[left] === s[right]) {
      // 取当前子回文串跟 max 对比即可
      const curr = s.slice(left, right + 1)
      max = curr.length > max.length ? curr : max

      // 往两边扩散
      left--
      right++
    }
  }

  return max
}

Rust

Tips

纪念一下, 第一次用 Rust 刷题. -- 2022/10/11

pub fn longest_palindrome(s: String) -> String {
    let n = s.len();
    let s_byte = s.as_bytes();
    let mut max = "";

    for i in 0..(n * 2 - 1) {
        let mut left = i / 2;
        let mut right = left + i % 2;

        while left < n && right < n && s_byte[left] == s_byte[right] {
            let curr = &s[left..=right];
            if curr.len() > max.len() {
                max = curr;
            }

            left -= 1;
            right += 1;
        }
    }

    max.to_string()
}

复杂度分析

• 时间复杂度: O(n²)
• 空间复杂度: O(n)