# 解法1deflongestPalindrome(self, s:str)->str:
n =len(s)if n ==0:return""
res = s[0]for i inrange(n -1):# 以自身为中心点
e1 = self.extend(i, i, s)# 以自身和自身的下一个元素为中心点
e2 = self.extend(i, i +1, s)ifmax(len(e1),len(e2))>len(res):
res = e1 iflen(e1)>len(e2)else e2
return res
defextend(self, i:int, j:int, s:str)->str:while i>=0and j <len(s)and s[i]== s[j]:
i -=1
j +=1return s[i +1: j]
# 解法2classSolution:deflongestPalindrome(self, s:str)->str:
n =len(s)if n <2:return s
max_len =1
begin =0# dp[i][j] 表示 s[i..j] 是否是回文串
dp =[[False]* n for _ inrange(n)]for i inrange(n):
dp[i][i]=True# 递推开始# 先枚举子串长度for L inrange(2, n +1):# 枚举左边界,左边界的上限设置可以宽松一些for i inrange(n):# 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
j = L + i -1# 如果右边界越界,就可以退出当前循环if j >= n:breakif s[i]!= s[j]:
dp[i][j]=Falseelse:if j - i <3:
dp[i][j]=Trueelse:
dp[i][j]= dp[i +1][j -1]# 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置if dp[i][j]and j - i +1> max_len:
max_len = j - i +1
begin = i
return s[begin:begin + max_len]if __name__ =="__main__":
s = Solution()
test_s ="aabbccdd"
result = s.longestPalindrome(test_s)print(result)