LeetCode 5. Longest Palindromic Substring 题解

LeetCode 5. Longest Palindromic Substring 题解题目描述给你一个字符串s找到s中最长的回文子串。示例 1输入s babad 输出bab 解释aba 同样是符合题意的答案。示例 2输入s cbbd 输出bb解题思路中心扩展法以每个字符为中心向两边扩展考虑两种情况长度为奇数的回文和长度为偶数的回文记录最长回文子串的起始和结束位置代码实现def longestPalindrome(s): def expand_around_center(left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return left 1, right - 1 start, end 0, 0 for i in range(len(s)): # 奇数长度的回文 l1, r1 expand_around_center(i, i) # 偶数长度的回文 l2, r2 expand_around_center(i, i 1) # 更新最长回文子串 if r1 - l1 end - start: start, end l1, r1 if r2 - l2 end - start: start, end l2, r2 return s[start:end1]复杂度分析时间复杂度O(n²)空间复杂度O(1)动态规划解法def longestPalindrome(s): n len(s) if n 2: return s dp [[False] * n for _ in range(n)] start, max_len 0, 1 # 长度为 1 的回文 for i in range(n): dp[i][i] True # 长度为 2 的回文 for i in range(n-1): if s[i] s[i1]: dp[i][i1] True start i max_len 2 # 长度 3 的回文 for length in range(3, n1): for i in range(n - length 1): j i length - 1 if s[i] s[j] and dp[i1][j-1]: dp[i][j] True if length max_len: start i max_len length return s[start:startmax_len]测试案例# 测试案例 1 assert longestPalindrome(babad) in [bab, aba] # 测试案例 2 assert longestPalindrome(cbbd) bb # 测试案例 3 assert longestPalindrome(a) a # 测试案例 4 assert longestPalindrome(ac) in [a, c]总结本题是回文子串问题的经典题目。关键点中心扩展法考虑奇数和偶数长度动态规划状态转移记录最长回文的起始和结束位置通过本题可以深入理解回文问题的解决方法。