那些年我们集过的卡片

神の安♂排

最长回文子串可不简单

#找奇数回文串 def oddfun(i,l): left = i - 1 right = i + 1 while left &gt;= 0 and right &lt;= len(l)-1: if l[left] == l[right]: left -= 1 right += 1 else: break return l[left+1:right] #向左找偶数回文串 def levenfun(i, l): left = i-1 right = i while left &gt;= 0 and right &lt;= len(l)-1: if l[left] == l[right]: left -= 1 right += 1 else: break return l[left+1:right] #向右找偶数回文串 def revenfun(i, l): left = i right = i + 1 while left &gt;= 0 and right &lt;= len(l) - 1: if l[left] == l[right]: left -= 1 right += 1 else: break return l[left+1:right] def solve_it(l): ls = [] #遍历L的索引 for i in range(1,len(l)-1): l1 = oddfun(i,l) l2 = levenfun(i,l) l3 = revenfun(i, l) #把找到的回文串添加到列表中 ls.extend([l1,l2,l3]) #把列表中最长的回文串的长度找到 le = max(len(x) for x in ls) #遍历列表拿出最长的字符串 for x in ls: if len(x) == le: return x print(solve_it(L))#这个暴力匹配时间复杂度略高# L = &quot;caayyhheejhhbbbhhjhhyyaac&quot; # def solve_it(l): # for i in range(len(l),1,-1): # for j in range(len(l)-i+1): # stmp = l[j:j+i] # if stmp == stmp[::-1]: # return stmp # print(solve_it(L))

较长，原理简单，时间复杂度O（n²）

<pre><code>s = &#x27;&#x27; max_len = 1 # 找奇数的 for i in range(1, len(L)): if len(L) - i &lt;= max_len // 2: break else: c = 1 step = 1 while i - step &gt;= 0 and i + step &lt; len(L): if L[i - step] == L[i + step]: step += 1 else: break c = 2 * step - 1 if c &gt; max_len: max_len = c s = L[i - step + 1:i + step] # 找偶数的 for i in range(1, len(L)): if len(L) - i &lt;= max_len // 2: break elif L[i] != L[i - 1]: continue else: c = 1 step = 1 while i - 1 - step &gt;= 0 and i + step &lt; len(L): if L[i - 1 - step] == L[i + step]: step += 1 else: break c = 2 * step if c &gt; max_len: max_len = c s = L[i - step:i + step] print(s)</code></pre>

上面的在LeetCode里有漏洞。应该是下标有问题。
class Solution:
 def longestPalindrome(self, s: str) -> str:
 max_len = 1
 r = s[0]

 # 找奇数的
 for i in range(1, len(s)):
 if len(s) - i <= max_len // 2:
 break
 else:
 step = 0
 while i - step - 1 >= 0 and i + step + 1 < len(s):
 if s[i - step - 1] == s[i + step + 1]:
 step += 1
 else:
 break
 if step > max_len // 2:
 max_len = 2 * step + 1
 r = s[i - step:i + step + 1]
 # 找偶数的
 for i in range(1, len(s)):
 if len(s) - i <= max_len // 2:
 break
 elif s[i] != s[i - 1]:
 continue
 else:
 step = 0
 while i - 2 - step >= 0 and i + step + 1 < len(s):
 if s[i - 2 - step] == s[i + step + 1]:
 step += 1
 else:
 break
 if step + 1 > max_len // 2:
 max_len = 2 * step + 2
 r = s[i - step - 1:i + step + 1]
 return r


print(Solution.longestPalindrome(Solution, L))

不可思议，我成功了

length = 0 s = &quot;*&quot; + &quot;*&quot;.join(L) + &quot;*&quot; if L == &quot;&quot; or len(L) == 1: print(L) lens = len(s) for i in range(lens):     count = 0 while i - count-1 &gt;0 and i + count+1 &lt; len(s) and s[i-count-1] == s[i+count+1]:         count += 1 if 2*count &gt; length:             length = 2*count             a,b = i,count l = list(s[a-b:a+b+1]) while &quot;*&quot; in l:     l.remove(&quot;*&quot;) l = &quot;&quot;.join(l) print(l)

新手 过了但感觉有缺陷

<a href="http://www.gznb.xyz/posts/pythonTip-54-最长回文子串可不简单/">题解： http://www.gznb.xyz/posts/pythonTip-54-最长回文子串可不简单/</a>

l1={}l2={}if L[0]==L[1]: l2[0]=2for i in range(1,len(L)-2): if L[i]==L[i+1]: count=2 a=i m=1 while True: if a-m&lt;0 or a+1+m&gt;len(L)-1: break elif L[a-m]==L[a+1+m]: count += 2 m+=1 else: break l2[i]=count if L[i-1]==L[i+1]: count=3 a=i m=2 while True: if a-m&lt;0 or a+m&gt;len(L)-1: break elif L[a-m]==L[a+m]: count+=2 m+=1 else: break l1[i]=countd1=max(list(l1.values()))d2=max(list(l2.values()))if d1&gt;d2: for i in l1: if l1[i]==d1: p=i print(L[p-int((d1-1)/2):p+int((d1-1)/2)+1])else: for i in l2: if l2[i]==d2: p=i d=d2 print(L[p-int(d/2)+1:p+int(d/2)+1])

挺麻烦的解法

<pre class="prettyprint lang-py linenums">def longestPalindrome():
 '''
 中心扩展
 :return:
 '''
 global L1

 L = L1 + '#'

 maxlen = 0
 start = 0
 start_index_list = []#考虑到最长回文子串存在多个值，这里记录多个起点的索引
 index_dict = {}#用于存放字符串中每个字符连续出现的次数以及起始索引
 for i in range(len(L)):
 if i &gt;= sum(index_dict.values()):
 for j in range(i+1,len(L)+1):
 if len(set(L[i:j])) != 1:
 index_dict[i] = len(L[i:j-1])
 break

 for k,v in index_dict.items():
 i = k - 1
 j = k + v
 while i &gt;= 0 and j &lt; len(L):
 if L[i] == L[j]:
 if maxlen &lt; j - i + 1:
 maxlen = j - i + 1
 start = i
 elif maxlen == j - i + 1:
 start_index_list.append(i)
 i -= 1
 j += 1
 else:
 break

 start_index_list.insert(0,start)
 if maxlen &gt;= 2:
 return [L[index:index+maxlen] for index in start_index_list]
 return None</pre> 详情可阅读：<a href="https://blog.csdn.net/Herishwater/article/details/95923488">https://blog.csdn.net/Herishwater/article/details/95923488</a>

基于中心扩展法进行的优化

<div style="color: rgb(171, 178, 191); background-color: rgb(40, 44, 52); font-family: Consolas, &quot;Courier New&quot;, monospace; font-size: 16px; line-height: 22px; white-space: pre;"><div>from collections import deque</div> <div>s = 'abccba'</div><div>q = deque()</div><div>length = len(s)</div><div>anwer = ''</div><div>#去除s太短的情况</div><div>if length ==1 or length == '':</div><div> anwer = s</div><div>if length ==2:</div><div> if s[0] == s[1]:</div><div> anwer = s</div><div> else:</div><div> anwer = s[0]</div> <div>#s &gt; 2时</div> <div>if length &gt; 2:</div><div> #先将所有两个三个形成的回文串找出来加入到队列中,</div><div> for i in range(0,length-2):</div><div> if s[i] == s[i+1]:</div><div> q.appendleft((i,i+1))</div><div> if s[i] == s[i+2]:</div><div> q.appendleft((i,i+2))</div><div> if s[-1] == s[-2]:</div><div> q.append((length-2,length-1))</div><div> </div><div> maxlen = 0</div><div> res = []</div><div> while len(q) &gt; 0:</div><div> tr = q.pop()</div><div> start,end = tr</div><div> res = (start,end+1)</div><div> if end+1&lt;=length-1 and start-1 &gt;= 0 :</div><div> if s[end+1] == s[start-1]:</div><div> q.appendleft((start-1,end+1))</div> <div> anwer = s[res[0]:res[1]]</div> <div>print(anwer)</div></div>

过了过了

def find(left,right,count): &nbsp; &nbsp; while L[left]==L[right]: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count+=2 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if left==0 or right==len(L)-1: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; left-=1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; right+=1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; return count length=0 s=len(L)//2 for i in range(0,len(L)): &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; s=s+(-1)**i*i &nbsp; &nbsp; if min(s,len(L)-1-s)&gt;=length//2:&nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if s-1&gt;=0 and L[s-1]==L[s]: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count=find(s-1,s,0) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if count&gt;length or (count==length and s&lt;index): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; length=count &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index=s &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag=0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if s+1&lt;len(L) and s-1&gt;=0 and L[s-1]==L[s+1]: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count=find(s-1,s+1,1) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if count&gt;length or (count==length and s&lt;index): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; length=count &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index=s &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag=1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; break if length&gt;0: &nbsp; &nbsp; print (L[index-length//2:index+length//2+flag]) else: &nbsp; &nbsp; print ('No answer')#多个回文取第一个

中心摇摆

L = &quot;caayyhheehhbbbhhjhhyyaac&quot; #L=&quot;abcbd&quot; def fun(L): 	start=0 	maxlen=1 	l=[[0 for i in L] for j in L] 	for i in range(len(L)): 		l[i][i]=1 		if i&lt;len(L)-1 and L[i]==L[i+1]: 			l[i][i+1]=1 			start=i 			maxlen=2 	for n in range(3,len(L)+1): 		for i in range(0,len(L)-n+1): 			j=i+n-1 			if l[i+1][j-1]==1 and L[i]==L[j]: 				l[i][j]=1 				start=i 				maxlen=n 	print(L[start:start+maxlen]) def fun1(L): 	start=0 	maxlen=1 	for i in range(0,len(L)): 		j=i-1 		k=i+1 		while(j&gt;=0 and k&lt;len(L) and L[j]==L[k]): 			if k-j+1&gt;maxlen: 				maxlen=k-j+1 				start=j 			j-=1 			k+=1 	for i in range(0,len(L)): 		j=i 		k=i+1 		while(j&gt;=0 and k&lt;len(L) and L[j]==L[k]): 			if k-j+1&gt;maxlen: 				maxlen=k-j+1 				start=j 			j-=1 			k+=1 	print(L[start:start+maxlen]) fun(L) fun1(L)

DP超时，只好用中心法

L2=[] for i in range(len(L)): &nbsp; &nbsp; L2.append('0') &nbsp; &nbsp; L2[i]=L[i] k=1 for i in range(len(L)-1): &nbsp; &nbsp;L2.insert(k,'#') &nbsp; &nbsp;k+=2 mas=0 ll=0 l=len(L2) for i in range(1,len(L2)-1): &nbsp; &nbsp; j=1 &nbsp; &nbsp; while i-j&gt;=0 and i+j&lt;=l-1: &nbsp; &nbsp; &nbsp; &nbsp; if L2[i-j]!=L2[i+j]: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break &nbsp; &nbsp; &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j+=1 &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if j&gt;ll: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ll=j &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mas=i L3=L2[mas-ll+1:mas+ll] while ('#' in L3): &nbsp; &nbsp; L3.remove('#') print (''.join(L3)) &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp;&nbsp;

enmmmm

class Solution: def longestPalindrome(self, s: str) -&gt; str:         max_len = 1         r = s[0] # 找奇数的 for i in range(1, len(s)): if len(s) - i &lt;= max_len // 2: break else:                 step = 0 while i - step - 1 &gt;= 0 and i + step + 1 &lt; len(s): if s[i - step - 1] == s[i + step + 1]:                         step += 1 else: break if step &gt; max_len // 2:                     max_len = 2 * step + 1                     r = s[i - step:i + step + 1] # 找偶数的 for i in range(1, len(s)): if len(s) - i &lt;= max_len // 2: break elif s[i] != s[i - 1]: continue else:                 step = 0 while i - 2 - step &gt;= 0 and i + step + 1 &lt; len(s): if s[i - 2 - step] == s[i + step + 1]:                         step += 1 else: break if step + 1 &gt; max_len // 2:                     max_len = 2 * step + 2                     r = s[i - step - 1:i + step + 1] return r print(Solution.longestPalindrome(Solution, L))

通过了

res = &#x27;&#x27; for i in range(0, len(L)-1):     cnt1, cnt2 = L[i], &#x27;&#x27;     left, right = i - 1, i + 1 while left &gt;= 0 and right &lt; len(L) and L[left] == L[right]:         cnt1 = L[left] + cnt1 + L[right]         left -= 1         right += 1 if L[i] == L[i+1]:         cnt2 = L[i] + L[i]         left, right = i - 1, i + 2 while left &gt;= 0 and right &lt; len(L) and L[left] == L[right]:             cnt2 = L[left] + cnt2 + L[right]             left -= 1             right += 1     cnt1 = (cnt2 if len(cnt1) &lt; len(cnt2) else cnt1)     res = (cnt1 if len(res) &lt; len(cnt1) else res) print(res)

暴力枚举

回文字串不是偶数个吗

应该采用特判，然而貌似是直接用manach,采用二分从第一位开始查找的nlogn答案错误

如果最长的子串有多个返回哪个

s1 = 0; s11 = &quot;&quot;; s2 = 0; s22 = &quot;&quot;; for i in range(1,len(L)-1): &nbsp; &nbsp; count1 = 1; &nbsp; &nbsp; str1 = L[i]; &nbsp; &nbsp; k=1; &nbsp; &nbsp; while i-k&gt;=0 and i+k&lt;len(L) and L[i-k]==L[i+k]: &nbsp; &nbsp; &nbsp; &nbsp; count1 +=2; &nbsp; &nbsp; &nbsp; &nbsp; str1 = L[i-k]+str1+L[i+k]; &nbsp; &nbsp; &nbsp; &nbsp; k +=1; &nbsp; &nbsp; if count1&gt;s1: &nbsp; &nbsp; &nbsp; &nbsp; s1 = count1; &nbsp; &nbsp; &nbsp; &nbsp; s11 = str1; for i in range(1,len(L)): &nbsp; &nbsp; count2 = 0; &nbsp; &nbsp; str2 = &quot;&quot;; &nbsp; &nbsp; k=1; &nbsp; &nbsp; while i-k&gt;=0 and i+k-1&lt;len(L) and &nbsp;L[i+k-1]==L[i-k]: &nbsp; &nbsp; &nbsp; &nbsp; count2 +=2; &nbsp; &nbsp; &nbsp; &nbsp; str2 = L[i-k]+str2+L[i+k-1]; &nbsp; &nbsp; &nbsp; &nbsp; k +=1; &nbsp; &nbsp; if count2&gt;s2: &nbsp; &nbsp; &nbsp; &nbsp; s2 = count2; &nbsp; &nbsp; &nbsp; &nbsp; s22 = str2; print [s11,s22][s1&lt;s2];

# 挑战成功了！！L = '#'.join(list(L)) # len is odd now! l = len(L) o,r=0,0 # 圆心，半径(不计圆心) for i in range(1,l): &nbsp;&nbsp;&nbsp; if i+r&lt;l and L[i-r:i] == L[i+r:i:-1]: # 移到:最右方便来计算 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; o,r=i,r &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; while i+r+1&lt;l and L[i-r-1] == L[i+r+1]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; r += 1 &nbsp;&nbsp;&nbsp; # print L[o-r:o+r+1] L1 = L[o-r:o+r+1] t1,t2 = L1[::2],L1[1::2] print t1 if any(i!='#' for i in t1) else t2

L = &quot;aayyhheehhbbbhhj&quot; L = '#'.join(list(L)) # len is odd now! l = len(L) o,r=0,0 # 圆心，半径(不计圆心) for i in range(1,l): &nbsp;&nbsp;&nbsp; if o+r==i-1 and L[i]==L[o-r-1]: # fix-bug: 能涨先涨再移位。 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; o,r=o,r+1 &nbsp;&nbsp;&nbsp; if i+r&lt;l and L[i-r:i] == L[i+r:i:-1]: # 移到:最右方便来计算 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; o,r=i,r &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; while L[i-r-1] == L[i+r+1]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; r += 1 L1 = L[o-r:o+r+1] t1,t2 = L1[::2],L1[1::2] if any(i!='#' for i in t1): &nbsp;&nbsp;&nbsp; print t1 else: &nbsp;&nbsp;&nbsp; print t2

L = &quot;aayyhheehhbbbhhj&quot; L = '#'.join(list(L)) # len is odd now! l = len(L) o,r=0,0 # 圆心，半径(不计圆心) for i in range(1,l): &nbsp;&nbsp;&nbsp; if o==i-1: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if i+r+1&lt;l and L[i-r-1:i] == L[i+r+1:i:-1]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; o,r=i,r+1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; print L[o-r:o+r+1] &nbsp;&nbsp;&nbsp; else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if o+r==i-1 and L[i]==L[o-r-1]: # fix-bug: 能涨先涨再移位。 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; o,r=o,r+1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if i+r&lt;l and L[i-r:i] == L[i+r:i:-1]: # 移到:最右方便来计算 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; o,r=i,r &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; print L[o-r:o+r+1] L1 = L[o-r:o+r+1] t1,t2 = L1[::2],L1[1::2] if any(i!='#' for i in t1): &nbsp;&nbsp;&nbsp; print t1 else: &nbsp;&nbsp;&nbsp; print t2 &nbsp;&nbsp; &nbsp; print o,r,L1,t1,t2

用Manacher啊。。虽然我也不会。。

a,b = 0,1 c = 0 for i in range(len(L)): &nbsp;&nbsp;&nbsp; if c-1&gt;=0 and L[c-1]==L[i]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; c -= 1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if i+1-c &gt; b-a: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a,b = c,i+1 &nbsp;&nbsp;&nbsp; elif L[c:i+1] == L[c:i+1][::-1]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if i+1-c &gt; b-a: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a,b = c,i+1 &nbsp;&nbsp;&nbsp; else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; c = i print L[a:b]# 当 L = &quot;hhbbbhhbbb&quot; ，历遍到第四个b时出现bug

GodIsCoding，你是线性高手，请问如何线性解决？

m,n = 0,0 for i in range(len(L)): &nbsp;&nbsp;&nbsp; for j in range(i+1-(n-m)): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if L[j:i+1]==L[j:i+1][::-1]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; m,n = j,i+1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; print L[m:n]

第54题：最长回文子串可不简单

判断三角形

本原串

吃糖果

简单题之列表转换