TNotes.leetcode

Appearance

0005. 最长回文子串【中等】

0005. 最长回文子串【中等】 ​

1. 📝 题目描述 ​

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

  • 回文性：如果字符串向前和向后读都相同，则它满足回文性。
  • 子字符串：子字符串是字符串中连续的非空字符序列。

示例 1：

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

解释：“aba”同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

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

2. 🎯 s.1 - 中心扩散 ​

c
void centerSpread(char* s, int len, int l, int r, int* start, int* maxLen) {
    while (l >= 0 && r < len && s[l] == s[r]) {
        l--;
        r++;
    }
    // 回退一步到最后匹配位置
    l++;
    r--;
    int curLen = r - l + 1;
    if (curLen > *maxLen) {
        *maxLen = curLen;
        *start = l;
    }
}

char* longestPalindrome(char* s) {
    int len = strlen(s);
    if (len < 2)
        return s;

    int start = 0, maxLen = 1;
    for (int i = 0; i < len - 1; i++) {
        centerSpread(s, len, i, i, &start, &maxLen);     // 奇数中心
        centerSpread(s, len, i, i + 1, &start, &maxLen); // 偶数中心
    }

    char* ans = (char*)malloc((maxLen + 1) * sizeof(char));
    strncpy(ans, s + start, maxLen);
    ans[maxLen] = '\0';
    return ans;
}
js
var longestPalindrome = function (s) {
  const len = s.length

  if (len < 2) return s

  let maxLen = 0
  let ans = [0, 1]
  // ans[0] 记录起始位置
  // ans[1] 记录长度

  for (let i = 0; i < len - 1; i++) {
    const odd = centerSpread(s, i, i)
    const even = centerSpread(s, i, i + 1)
    const max = odd[1] > even[1] ? odd : even
    if (max[1] > maxLen) {
      ans = max
      maxLen = max[1]
    }
  }

  return s.slice(ans[0], ans[0] + ans[1])
}

function centerSpread(s, l, r) {
  let len = s.length
  while (l >= 0 && r <= len - 1) {
    // 如果不相等，结束循环
    if (s[l] !== s[r]) break

    // 如果相等，则继续往两侧扩散，准备下一次判断
    l--
    r++
  }
  // 两侧各回退到上一步所在的位置（while 循环结束有两种可能：1. 有指针溢出；2. 不满足扩散条件）
  l++
  r--
  return [l, r - l + 1]
}
py
class Solution:
    def longestPalindrome(self, s: str) -> str:
        def centerSpread(l, r):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            # 回退一步到最后匹配位置
            return l + 1, r - l - 1  # (start, length)

        start, max_len = 0, 1
        for i in range(len(s) - 1):
            for l, r in [(i, i), (i, i + 1)]:  # 奇数中心 / 偶数中心
                s0, cur_len = centerSpread(l, r)
                if cur_len > max_len:
                    start, max_len = s0, cur_len

        return s[start : start + max_len]
  • 时间复杂度：O(n2)，枚举 n 个中心，每次扩散最多 O(n)
  • 空间复杂度：O(1)，只使用常数额外空间

算法思路：

  • 回文串有两种形态：奇数长度（单字符中心）和偶数长度（双字符中心），以每个位置 i 为中心分别做一次扩散
  • centerSpread(s, l, r)：从 l、r 向两侧扩散，只要 s[l] === s[r] 就继续，直到越界或字符不等，返回 [起始下标, 长度]
  • 每次取奇偶两种扩散结果中较长的，与全局最优比较并更新

Discussions