题解 | #密码截取#

密码截取

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


# 从右到左,对每个字符进行遍历处理,并且每个字符要处理两次,因为回文子串有两种情况:
# ABA型:只需要从当前字符向两边扩散,比较左右字符是否相等,找出以当前字符为中心的最长回文子串长度
# ABBA型:只需要从当前字符和下一个字符向两边扩散,比较左右字符是否相等,找出以当前字符和下一个字符为中心的最长回文子串长度
# 最后比对两种类型的长度,取自较长的长度
out = 0

for i in range(0, len(s)):  # 双指针
    k = i - 1
    j = i + 1
    len_ABA = 1
    while k >= 0 and j < len(s):
        if s[k] == s[j]:
            k -= 1
            j += 1
            len_ABA += 2
        else:
            break
    
    k = i
    j = i + 1
    len_ABBA = 0
    while k >= 0 and j < len(s):
        if s[k] == s[j]:
            k -= 1
            j += 1
            len_ABBA += 2
        else:
            break
     
    now_len = max(len_ABA, len_ABBA)
    if out <now_len:
        out = now_len
print(out)
全部评论
标签里的动态规划咋来的
1 回复 分享
发布于 2024-04-19 21:43 浙江
我可以说,我连题目都没读懂嘛,更别说,分成ABA ABBA型了,看完,才恍然大悟
1 回复 分享
发布于 2023-06-08 16:01 广东
为什么要比较out和now_len的值呢?直接输出now_len不行吗?
1 回复 分享
发布于 2022-11-27 18:16 四川
思路清晰,理解起来比较简单,点赞作者!
1 回复 分享
发布于 2022-04-11 17:53
你这是扩展法解决回文子串问题,题目的标签是”动态规划“
点赞 回复 分享
发布于 2024-12-13 10:53 上海
太优雅了
点赞 回复 分享
发布于 2023-07-18 19:24 江苏
nice,这种方法很好
点赞 回复 分享
发布于 2023-03-30 22:59 天津
# 暂时不明白这里为什么一个设置 1 一个设置 0 len_ABA = 1 len_ABBA = 0
点赞 回复 分享
发布于 2022-09-11 21:46 浙江
太优雅了
点赞 回复 分享
发布于 2022-08-21 00:08 安徽
6666
点赞 回复 分享
发布于 2022-08-02 18:47
这个牛逼
点赞 回复 分享
发布于 2022-05-25 22:41
点赞
点赞 回复 分享
发布于 2022-05-09 22:14

相关推荐

昨天 10:56
门头沟学院 Java
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
评论
116
34
分享

创作者周榜

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