Python算法题----取出最长回文子串
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.穷举法
取出所有的子串组合，挨个判断，返回最长的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
def isPalindrome(self, s, start, end):
while start < end:
if s != s:
return False
start += 1
end -= 1
return True
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
max, left, right = 0, 0, 0
for i in range(len(s)):
j = i+1
while j < len(s):
if self.isPalindrome(s, i, j):
if (j-i+1) > max:
left, right = i, j
max = j - i + 1
j += 1
print left, right, max
return s
双指针两边扩展
遍历指针为i， j=i+1， i左移，j右移。判断是否相等将长度，下标赋给临时变量，最后切片返回。唯一的大坑。回文字符串长度可以是奇数也可以是偶数。奇数的时候，内层循环从i-1开始。边界条件也需要处理好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
maxL, maxR, max = 0, 0, 0
for i in range(n):
# 长度为偶数的回文字符串
start = i
end = i + 1
while start >= 0 and end < n:
if s == s:
if end - start + 1 > max:
max = end - start + 1
maxL = start
maxR = end
start -= 1
end += 1
else:
break
# 长度为奇数的回文子串
start = i - 1
end = i + 1
while start >= 0 and end < n:
if s == s:
if end - start + 1 > max:
max = end - start + 1
maxL = start
maxR = end
start -= 1
end += 1
else:
break
return s
页:
[1]