Mahdi Shamlou | Solving LeetCode #5: 最长回文子串 — 我的中心扩展法冒险

Source: Dev.to

大家好！我是 Mahdi Shamlou —— 让 LeetCode 经典题目系列继续前进 🚀

在完成了 #4 Median of Two Sorted Arrays 之后，今天我们来聊聊第 5 题 —— Longest Palindromic Substring，这是另一个在大量面试中出现的超热门题目！

Problem Statement

给定一个字符串 s，返回 s 中最长的回文子串。
回文串在正向和反向阅读时是相同的。

示例

Input: s = "babad"
Output: "bab"
Explanation: "aba" 也是一个有效答案（长度均为 3）

Input: s = "cbbd"
Output: "bb"

Input: s = "a"
Output: "a"

Solution: Expand‑Around‑Center

刚开始考虑时，遍历所有可能的子串感觉非常痛苦（O(n³) 的噩梦 😅）。随后我意识到：回文可以从中心向两侧扩展！

思路是把每个字符（对应奇数长度的回文）以及每两个字符之间的间隙（对应偶数长度的回文）都当作潜在的中心，然后在两侧字符相等时不断向外扩展。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        start = 0
        end = 0

        def expand_around_center(left: int, right: int):
            while left >= 0 and right  end - start:
                start, end = l1, r1

            if r2 - l2 > end - start:
                start, end = l2, r2

            # Debug prints (optional)
            # print(f"start : {start} and end : {end}")
            # print("#" * 100)

        return s[start:end + 1]

Complexity Analysis

• 时间复杂度： O(n²) – 每次扩展最坏可达 O(n)，而中心大约有 2n 个。
• 空间复杂度： O(1) – 只使用了少量整数变量。

References

• 上一篇文章: Mahdi Shamlou | Solving LeetCode #4: Median of Two Sorted Arrays
• 完整的解题仓库: GitHub – mahdi0shamlou/LeetCode