题解 | #密码截取# 超详细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
如有帮助记得点赞~!~
全部评论
大佬,你好,我为什么用这个读取输入就只有两行输入啊: while True: try: s = input() print(s) except: break 提交答案后的第一个用例,答案里就不止两行,我这么读出来只有两行啊???
1 回复 分享
发布于 2021-08-12 15:18
既暴力又不简单,手动狗头
点赞 回复 分享
发布于 2023-02-01 20:31 北京
好暴力,哈哈n的三次方
点赞 回复 分享
发布于 2022-04-27 21:33

相关推荐

零OFFER战士:另一个版本查看图片
点赞 评论 收藏
分享
06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
评论
29
6
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务