题解 | #密码截取#

密码截取

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

这道题可以用动态规划,定义dp为表示两端索引为i,j的字符段是否回文串的二维数组,
可以参考********最长回文子串,但是这种解法空间复杂度为O(n2),占用内存过多,
我使用的是双指针,空间复杂度0(1),时间复杂度O(n2)。
思路就是遍历每个字符,由这个字符向两边扩展,两端字符相同继续扩展,同时更新最大长度,
否则退出循环,因为子串可能是奇数可能是偶数,所以需要两种情况分别遍历

code = input()
n = len(code)
if n<=1:
    print(code)
max_lo = 1
max_le = 0
for i in range(1,n-1):
    left,right = i-1,i+1
    while 0<=left<right<n and code[left]==code[right]:
        max_lo = max(max_lo,right-left+1)
        left-=1
        right+=1
for i in range(n-1):
    left,right = i,i+1
    while 0<=left<right<n and code[left]==code[right]:
        max_le = max(max_le,right-left+1)
        left-=1
        right+=1

print(max(max_lo,max_le))


全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务