题解 | #密码截取#

密码截取

http://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1

while 1:
    try:
        a=input()
        # 设置初始步长
        bc=0
        # 逆序比较
        if a==a[::-1]:
            print(len(a))
        else:
        # 不断增加步长,比较回文
        #每次增加步长,循环查找有没有比这个步长更长的回文,如果有,继续找,直到找完所有的回文为止
            for i in range(len(a)):
            #     优先查看两个增加两个长度的回文是否存在
                if i-bc>=1 and a[i-bc-1:i+1]==a[i-bc-1:i+1][::-1]:
                    bc+=2
            #     如果增加两个长度的没找到,再查看两个增加一个长度的回文是否存在
                elif  i-bc>=0 and a[i-bc:i+1]==a[i-bc:i+1][::-1]:
                    bc+=1
            print(bc)
    except:
        break
全部评论
看了好几遍硬是没看懂
1 回复 分享
发布于 2022-08-11 16:10
大佬,你的解法为何如此清新脱俗,主流的二维动态数组的解法我能看懂,你的解法我看不懂,只晓得解法很快,能不能解释一下,完全摸不到头脑!膜拜!!
点赞 回复 分享
发布于 2022-05-09 22:28
我也没看懂
点赞 回复 分享
发布于 2022-08-17 15:10 浙江
if i-bc>=1或if i-bc>= 0 是确保字符串索引至少是0,不至于出现a[-1]的情况,为什么bc+=1或bc+=2,是因为正逆序对比的差值就是bc+1或bc+2,所以相当于把比对成功后的步长赋予原步长。
点赞 回复 分享
发布于 2022-09-07 15:43 江苏
我理解的是历遍过程中判断某一个节点是否比先前的步长条件,多一个步长的情况下也对称,若有则一直叠加,没有的话则这个为最长
点赞 回复 分享
发布于 2023-04-05 18:50 广东
我粗浅做一个解释,这个解法的核心思路是动态规划: 假设当下有长度为s的字符串,其最长回文为max_n. 再增加一个字符构建s+1长度字符串,若出现超过最大长度可能,那必然是新增字符导致,然后看分别看从后往前max_n+1 和 max_n +2 两种情况是否构成新的回文.若构成了,更新max_n;若未构成,最长回文依旧是原来的max_n. 从1到‘输入字符串真实长度a’重复上述循环,则求得长回文。
点赞 回复 分享
发布于 2023-05-14 19:42 北京
这个所谓的步长其实应该叫当前最长回文字符串的长度,随着遍历i的过程中i的增加做两类判断,一类是ABBA,往前往后分别多取一个字符,如果i-max-1:i+1是回文,则最大回文串长度+2,另一类是ABA,往前多取一个字符,如果i-max:i+1是回文串则最大回文串长度+1,以最大长度为中心的解法,和另一个解答里的按某个字符为中心的扩散解法类似,都非常奈斯
点赞 回复 分享
发布于 2023-09-24 20:44 广东
还可以化简一下 while True: try: a = input() b = 0 if a==a[::-1]: print(len(a)) else: for i in range(len(a)): if a[i-b:i+1]==a[i-b:i+1][::-1]: b+=1 print(b) except: break
点赞 回复 分享
发布于 04-02 09:55 北京

相关推荐

11-09 12:17
清华大学 C++
out11Man:小丑罢了,不用理会
点赞 评论 收藏
分享
评论
20
10
分享
牛客网
牛客企业服务