题解 | #密码截取# 超详细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
好暴力,哈哈n的三次方
点赞 回复 分享
发布于 2022-04-27 21:33
既暴力又不简单,手动狗头
点赞 回复 分享
发布于 2023-02-01 20:31 北京

相关推荐

ProMonkey2024:5个oc?厉害! 但是有一个小问题:谁问你了?😡我的意思是,谁在意?我告诉你,根本没人问你,在我们之中0人问了你,我把所有问你的人都请来 party 了,到场人数是0个人,誰问你了?WHO ASKED?谁问汝矣?誰があなたに聞きましたか?누가 물어봤어?我爬上了珠穆朗玛峰也没找到谁问你了,我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒,在找到谁问你之前我连癌症的解药都发明了出来,我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了(别的帖子偷来的,现学现卖😋)
点赞 评论 收藏
分享
评论
29
6
分享
牛客网
牛客企业服务