题解 | #密码截取#

密码截取

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

从头开始遍历,后面若有更长的对称段,必定随着遍历的进行,长度不断从旧的对称段长度开始增大

这样可以把时间压到50ms左右

def isSymmetric(s):
    return s==s[::-1]

s=input()
maxL=1
# 以l和r标记对称段
l,r=0,1
for i in range(1,len(s)):
    # 若第i个字符和对称段结尾相邻
    if i==r:
        # 若对称段向左右各扩展一位后对称
        if l>0 and isSymmetric(s[l-1:i+1]):
            l-=1
            r+=1
        # 若对称段向右扩展一位后对称
        elif isSymmetric(s[l:i+1]):
            r+=1
        else:
            pass
    # 若第i个字符和对称段结尾不相邻
    else:
        count=0
        # 从第i个字符往前maxL-1个字符开始往前搜索更长的对称段
        for j in range(i+1-maxL,r-2,-1):
            if isSymmetric(s[j:i+1]):
                l=j
                r=i+1
                count=0
            # 考虑到长度的奇偶性,对称段可能会隔一次迭代出现:d,vd,dvd
            else:
                count+=1
                if count==2:
                    break
    maxL=r-l
print(maxL)

全部评论
滑动窗口
点赞 回复 分享
发布于 2024-05-21 08:30 江苏

相关推荐

不愿透露姓名的神秘牛友
07-01 17:13
想去,但是听说加班强度实在难崩,所以拒绝了,现在有点心梗对面hr感觉也是实习生,打电话的时候怪紧张的,但是感觉人很好嘞
水中水之下水道的鼠鼠:哥们这不先去体验一下,不行再跑呗,大不了混个实习经历(有更好的转正offer就当我没说)
点赞 评论 收藏
分享
那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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