易小侠 2022-02-01 13:12 采纳率: 93.9%
浏览 89
已结题

用python解决最长回文子串问题

最长回文子串
给你一个字符串 s,找到 s 中最长的回文子串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:

输入:s = "cbbd"
输出:"bb"
示例 3:

输入:s = "a"
输出:"a"
示例 4:

输入:s = "ac"
输出:"a"

  • 写回答

1条回答 默认 最新

  • Code_流苏 C/C++领域优质创作者 2022-02-01 14:56
    关注

    可以借助Manacher's Algorithm(马拉车算法)进行求解
    这个算法是以每一个字符为中心, 向两边发散,同时,用一个数组p来记录以每一个字符为中心的回文串的一半的长度.
    具体的可网上检索进行了解
    代码如下:

    class Solution:
        def longestPalindrome(self, s):
            def get_length(string, index):
                # 借助循环求出index为中心的最长回文字串
                start, length = index // 2, 0
               #获取字符串长度,并赋值非r_
                r_ = len(string)
                for i in range(1, index + 1):
                    if index + i < r_ and string[index - i] == string[index + i]:
                        start = (index - i) // 2
                        length += 1
                    else:
                        break
                return start, length
    
            s_list = [c for c in s]
    
            # 形成新串
            new_s = '#' + '#'.join(s_list) + '#'        
    
            #初始化赋值
            max_start = max_length = 0
            length = len(new_s)
            for index in range(0, length):
                start, r_length = get_length(new_s, index)
                if max_length < r_length:            #如果max_length小于r_length 则将start、r_length分别赋值给max_start、max_length
                    max_start, max_length = start, r_length
            return s[max_start: max_start+max_length]
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录

报告相同问题?

问题事件

  • 系统已结题 2月9日
  • 已采纳回答 2月1日
  • 创建了问题 2月1日

悬赏问题

  • ¥15 ikuai客户端多拨vpn,重启总是有个别重拨不上
  • ¥20 关于#anlogic#sdram#的问题,如何解决?(关键词-performance)
  • ¥15 相敏解调 matlab
  • ¥15 求lingo代码和思路
  • ¥15 公交车和无人机协同运输
  • ¥15 stm32代码移植没反应
  • ¥15 matlab基于pde算法图像修复,为什么只能对示例图像有效
  • ¥100 连续两帧图像高速减法
  • ¥15 如何绘制动力学系统的相图
  • ¥15 对接wps接口实现获取元数据