LeetCode热题100-最长回文子串

首先想到的就是暴力解法：时间复杂度On2

class Solution: def longestPalindrome(self, s: str) -> str: if not s: return "" length = len(s) max_long = s[0] def isPalind(s1: str) -> bool: s2 = s1[::-1] return s1 == s2 for i in range(length): for j in range(i + 1, length + 1): sub_str = s[i:j] if isPalind(sub_str) and len(sub_str) > len(max_long): max_long = sub_str return max_long

中心扩张方法，这里区分奇数扩张、偶数扩张

class Solution: def longestPalindrome(self, s: str) -> str: if not s: return "" def expend(l, r): while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1 r += 1 return s[l+1:r] max_long = s[0] for i in range(len(s)): s1 = expend(i, i) # 奇数扩张 s2 = expend(i, i+1) # 偶数扩张 max_long = max(max_long, s1, s2, key=len) return max_long