题目

Given a string s, find the longest palindromic substring in s.
You may assume that the maximum length of s is 1000.

Example:

1
2
3
4
5
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example:

1
2
3
Input: "cbbd"
Output: "bb"

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def longestPalindrome(self, s):
if len(s) > 1000:
raise ValurError
result = [0, 0, 0]
for i in range(0, len(s)):
for j in range(i+1, len(s)):
if s[i:j] == s[i:j][::-1]:
if len(s[i:j]) > result[2]:
result = [i, j, len(s[i:j])]
return result[i:j]

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def longestPalindrome(self, s):
if len(s) > 10000:
raise ValueError
def expandAroundCenter(st, left, right):
while left >= 0 and right < len(st) and st[left] == st[right]:
left, right = left-1, right+1
return right-left-1
start, end = 0, 0
for i in range(0, len(s)):
l1 = expandAroundCenter(s, i, i)
l2 = expandAroundCenter(s, i, i+1)
length = max(l1, l2)
if length > end - start:
start = i - (length -1) // 2
end = i + length // 2
return s[start:end+1]