最长回文子串LeetCode 第 5 题经典动态规划问题时间复杂度 O(n²)空间复杂度可优化至 O(1)。Python3 实现class Solution:def longestPalindrome(self, s: str) - str:if not s or len(s) 1:return start, end 0, 0for i in range(len(s)):len1 self.expandAroundCenter(s, i, i)len2 self.expandAroundCenter(s, i, i 1)max_len max(len1, len2)if max_len end - start:start i - (max_len - 1) // 2end i max_len // 2return s[start:end1]def expandAroundCenter(self, s: str, left: int, right: int) - int:while left 0 and right len(s) and s[left] s[right]:left - 1right 1return right - left - 1核心思路采用中心扩展法遍历每个字符作为回文中心向两边扩展寻找最长回文。需要处理两种中心情况奇数长度单个字符为中心和偶数长度两个相同字符为中心。时间复杂度O(n²)空间复杂度O(1)关键步骤1遍历字符串每个位置作为潜在回文中心。2分别以单个字符为中心奇数长度和相邻字符为中心偶数长度向两侧扩展。3比较两种扩展方式得到的回文长度取较大者更新全局最长回文区间。4根据最大长度计算起始和结束索引返回子串。示例验证输入babad输出bab或aba均为正确答案存在多个最长回文时返回任意一个即可。测试用例1sol Solution()2print(sol.longestPalindrome(babad)) # 输出: bab 或 aba3print(sol.longestPalindrome(cbbd)) # 输出: bb4print(sol.longestPalindrome(a)) # 输出: a
