LeetCode-5 最长回文子串

本文涉及的产品
实时计算 Flink 版,5000CU*H 3个月
检索分析服务 Elasticsearch 版,2核4GB开发者规格 1个月
大数据开发治理平台 DataWorks,不限时长
简介: LeetCode-5 最长回文子串

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/longest-palindromic-substring

题目描述

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

 

示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
示例 3:
输入:s = "a"
输出:"a"
示例 4:
输入:s = "ac"
输出:"a"
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母(大写和/或小写)组成

解题思路

解法1:

这道题第一眼看上去就需要用动态规划的算法,然鹅众所周知动态规划一直是楼主的弱项。。所以我使用了中心扩展算法。

对于第i个字母来说,如果他是回文子串的中心,那么他只能有两种状态:1、他是回文子串的中心 2、他与i+1个字母共同组成了回文子串的中心,并且值与i+1个字母相同。假设他们均满足这两种情况,以他们为中心向两边进行扩展,计算出状态1和状态2的长度,找出最长。用这个思路将字符串遍历一遍,然后返回最大值,这个题就解完了,但是就如结果所示那样,这个解法的时间复杂度是O(n2),时间较长,倒是另一种manacher算法很有趣,时间复杂度也更低。

解法2:

在解法1的中,每换一次中心就需要重新求一次回文子串,那么之前计算过的回文子串是不是可以简单的利用一下帮助之后的回文子串的生成?答案是肯定的。

首先为了将双中心子串,如abba的子串也变成单中心的子串,我们在每个字母中间加入了‘#’,这样abba子串会变成a#b#b#a单中心子串,而单中心子串aba变成了a#b#a也还是单中心子串。

先引入一个臂长的概念,如果以i为中心,回文长度为i + 2 * r的回文子串,那么,r就为i位置的臂长。

 

所以可以省去很多的比较。最终复杂度达到O(n)。

 

解法1:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 中心扩展算法
        if len(s) < 1: return ""
        L = 0
        R = 0
        i=0
        while i<len(s):
            len1 = Solution.kuozhan(self, i,i, s)
            len2 = Solution.kuozhan(self, i, i + 1, s)
            lenx = max(len1, len2)
            if lenx > R - L:
                L = i - (lenx - 1) // 2
                R = i + lenx // 2
            i+=1
        return s[L:R + 1]
    def kuozhan(self, start: int, end: int, s: str) -> int:
        L = start
        R = end
        while L >= 0 and R < len(s) and s[L] == s[R]:
            L -= 1
            R += 1
        return R - L - 1


解法2:

class Solution:
    def longestPalindrome(self, s: str) -> str:
       #Manacher 算法
        news="#"
        for c in s:
            news+=c
            news+='#'
        lenr=[]
        R=-1
        C=0
        p2=0
        p1=0
        cL=0
        pL=0
        maxx=0
        maxc=0
        while p1<len(news):
            if p1>R:
                r=Solution.kuozhan(self,p1,1,news)
                lenr.append(r)
                R=p1+r-1
                C=p1
            else:
                p2=2*C-p1
                pL=p2-lenr[p2]+1
                cL=C-lenr[C]+1
                if cL<pL:
                    lenr.append(lenr[p2])
                elif cL>pL:
                    lenr.append(R-p1+1)
                else:
                    r=Solution.kuozhan(self,p1,R-p1+1,news)
                    lenr.append(r)
                    R=p1+r-1
                    C=p1
            if lenr[-1]>maxx:
                maxx=lenr[-1]
                maxc=p1
            p1+=1
        return  news[maxc-maxx+1:maxc+maxx].replace('#','')
    def kuozhan(self,z:int,r:int,s: str) -> int:
        L = z-r
        R = z+r
        while L >= 0 and R < len(s) and s[L] == s[R]:
            L -= 1
            R += 1
        return R - z


运行结果

 

相关文章
|
7天前
|
算法
LeetCode算法题---最长回文子串、N 字形变换(四)
LeetCode算法题---最长回文子串、N 字形变换(四)
25 0
|
7天前
leetcode代码记录(最长回文子串
leetcode代码记录(最长回文子串
10 2
|
7天前
leetcode-5:最长回文子串
leetcode-5:最长回文子串
24 0
|
7天前
|
存储 算法 Go
LeetCode第五题: 最长回文子串
给定一个字符串 `s`​,找到 `s`​ 中最长的回文子串。你可以假设 `s`​ 的最大长度为 1000。
LeetCode第五题: 最长回文子串
|
7天前
|
算法 Go
golang力扣leetcode 5.最长回文子串
golang力扣leetcode 5.最长回文子串
30 1
|
7天前
|
算法 C#
Leetcode算法系列| 5. 最长回文子串
Leetcode算法系列| 5. 最长回文子串
|
10月前
【LeetCode 训练营 3,5】无重复字符的最长子串+最长回文子串
【LeetCode 训练营 3,5】无重复字符的最长子串+最长回文子串
54 1
|
7天前
|
算法
力扣5、 最长回文子串
力扣5、 最长回文子串
|
7月前
|
存储
力扣刷题-最长回文子串
力扣刷题-最长回文子串
|
8月前
|
算法
LeetCode5-最长回文子串
LeetCode5-最长回文子串