题解 | #密码截取# 超详细Python最简单非暴力解法 15行搞定
密码截取
http://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1
输入:‘1332ABBA707’ #输入中有‘ABBA’ 、'33'、'707'三个回文子串,长度分别为4,2,3,不难发现一个规律。偶数回文串中间必然存在2位的回文子串‘XX’,奇数回文串中间必然存在3位的回文子串'XYX'
输出:4 #'ABBA'长度为4最大,故输出4
解题思路:其实题目意思很简单,就是要找字符串中最长的回文串长度,暴力解法容易超时,所以要想办法尽量减少计算量
1、长度为1的任何一个字符都是回文串,默认输出1
2、长度大于1的任何一个回文串,要么是奇数回文串,要么是偶数回文串
3、所以只要在字符串中找长度为2的偶数回文子串或者长度为3的奇数回文子串,然后在找到的回文子串两边各加一个数,看是否依旧回文,直到不是回文了就跳出,判断该回文串长度与结果比较保存最大值即可
while True: try: s = input() res = 1 #默认最长回文串为1 for lenth in range(2,4): #偶数回文串起始中间长度为2,奇数回文串为3,循环两次即可 for i in range(len(s)-lenth+1): #根据回文子串长度遍历列表,i是起始下标 if s[i:i+lenth] == s[i:i+lenth][::-1]: #如果发现回文子串 for x in range(min(i,len(s)-i-lenth)+1): #限制条件,避免下标溢出 if s[i-x:i+lenth+x] == s[i-x:i+lenth+x][::-1]: #在发现的最小回文子串两边不断加上一个数再判断是否依旧回文 res = max(res,lenth+2*x) #如果满足回文则比较是否比res大,如果因为可能有多个回文子串,取最大值 else: break #如果加了之后不是回文了,说明该回文子串已经找到了最大的长度,那么跳出循环继续找别的回文字符串 print(res) except: break
如有帮助记得点赞~!~