第一思路 先写个判断回文的函数
def judge(list1): print(list1[0:0]) low = 0 high = len(list1)-1 if high <= 0: return True while low < high: if list1[low] == list1[high]: low += 1 high -= 1 else: break if low <high or list1[low] != list1[high]: return False else: return True
然后以每个字母为头去判断回文长度
发现根本不靠谱 因为有的短的不是回文 长的却是 这时间复杂度上天了
下面这个是错的
def long(s): length = 1 maxlen = 1 for i,each in enumerate(s): while i+length < len(s): if judge(s[i:i+length]) : length += 1 else: break if length-1 > maxlen: maxlen = length-1 length = 1 return maxlen print(long('aba'))
后面想着以每个回文中心作为判断依据
但是要注意 中心可能在两个字母中间 所以有了以下的代码
:
def judge2(s): i = 0 high = len(s)-1 maxlen = 0 maxpos = 0 while i <= high: if i % 1 == 0: i = int(i) j = 0 while (i-j)>=0 and (i+j)<=high: if s[i-j] == s[i+j]: length = 1+j*2 else: break if length > maxlen: maxpos = int(i) maxlen = length j += 1 else: j = 0 ilow = int(i//1) while (ilow-j)>=0 and (ilow+1+j)<=high: if s[ilow-j] == s[ilow+1+j]: length = j*2+2 else: break if length > maxlen: maxpos = int(ilow) maxlen = length j += 1 i = i +0.5 maxpos = int(maxpos) maxlen = int(maxlen) if maxlen %2 == 0: return s[maxpos-maxlen//2+1:maxpos+maxlen//2+1] else: return s[maxpos-maxlen//2:maxpos+maxlen//2+1]
每次步进0.5往后便历
如果不是整数 说明这一步在判断偶数个字母组成的回文.