longest palindromic substring

Description


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

Solution


这是一个字符串问题,我最初的想法是:先找出成对出现字符的索引,按两个字符索引直接的距离排序,判断是否是回文序列,输出。但是这个方法在有大段重复字符的情况下表现太差了。
代码如下,尝试修改了一下,但是治标不治本

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
def (item):
return item[1] - item[0]
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) is 0: return ''
if len(s) is 1: return s
p = {}
for i in range(len(s)):
if s[i] in p.keys():
p[s[i]].append(i)
else:
p[s[i]] = [i]
pairs = []
for i in p.values():
if len(i) > 1:
for j in range(len(i)-1):
for k in range(1,len(i)):
pairs.append([i[j],i[k]])
if pairs == []: return s[0]

# for i in range(20):
# large = max(pairs,key=minus)
# subs = s[large[0]:large[1]+1]
# if subs == subs[::-1]:
# return subs
# pairs.remove(large)
pairs.sort(key=minus, reverse = True)
for i in pairs:
subs = s[i[0]:i[1]+1]
if subs == subs[::-1]:
return subs
return s[0]

在discussion里看到比较好的思想是种子向外扩展(扫描n个位置,分单复数的情况),进一步优化将连续重复字符略过,得到:

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):
'''
:type s: str
:rtype: str
'''
if len(s)<=1: return s
start,left,right=0,0,0 # init
while (start+int((right-left)/2)<len(s)):
i,j=0,1 # two pointer, i - repeat chars, j - palindrome step
while (start+i<len(s)-1): # find the repeat chars amount start+i+1<=len(s)-1
if s[start]==s[start+i+1]: i+=1
else: break
while(start-j>=0 and start+i+j<len(s)): # find the number of palindrome step
if s[start-j]==s[start+i+j]:j+=1
else: break
if (right-left<i-1+2*j):left,right=start-j+1,start+j+i
start=start+i+1
return s[left:right]