LeetCode 5. [Python] Longest Palindromic Substring
原题链接
中等
作者:
徐辰潇
,
2021-01-05 02:23:37
,
所有人可见
,
阅读 313
class Solution:
def longestPalindrome(self, s: str) -> str:
#TC: O(len(s))
#SC: O(1)
#Two situations:
#A. cbabc (odd central)
#B. cbaabc (even central)
n = len(s)
#basis case for situation A (s = 'a')
L = 1
res_start = 0
res_end = 0
#basis case for situation B (s = 'aa')
for i in range(n-1):
if s[i] == s[i+1]:
res_start = i
res_end = i+1
L = 2
#start from the central
#situation A
for i in range(1, n-1):
left = i
right = i
while(left >= 0 and right < n and s[left] == s[right]):
L_tmp = right - left + 1
if L_tmp > L:
L = L_tmp
res_start = left
res_end = right
left -= 1
right += 1
#start from the central
#situation B
for i in range(1, n-1):
left = i
right = i+1
while(left >= 0 and right < n and s[left] == s[right]):
L_tmp = right - left + 1
if L_tmp > L:
L = L_tmp
res_start = left
res_end = right
left -= 1
right += 1
return s[res_start:res_end+1]